{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum Lists LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #linked-list #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #链表 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: addTwoNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #链表求和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个用链表表示的整数，每个节点包含一个数位。</p>\n",
    "\n",
    "<p>这些数位是反向存放的，也就是个位排在链表首部。</p>\n",
    "\n",
    "<p>编写函数对这两个整数求和，并用链表形式返回结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>(7 -&gt; 1 -&gt; 6) + (5 -&gt; 9 -&gt; 2)，即617 + 295\n",
    "<strong>输出：</strong>2 -&gt; 1 -&gt; 9，即912\n",
    "</pre>\n",
    "\n",
    "<p><strong>进阶：</strong>思考一下，假设这些数位是正向存放的，又该如何解决呢?</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>(6 -&gt; 1 -&gt; 7) + (2 -&gt; 9 -&gt; 5)，即617 + 295\n",
    "<strong>输出：</strong>9 -&gt; 1 -&gt; 2，即912\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-lists-lcci](https://leetcode.cn/problems/sum-lists-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-lists-lcci](https://leetcode.cn/problems/sum-lists-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,3]\\n[5,6,4]', '[0]\\n[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        rev_l1 = self.reverseList(l1)\n",
    "        rev_l2 = self.reverseList(l2)\n",
    "        count = 0\n",
    "        ret = ListNode()\n",
    "        tmo = ret\n",
    "        while rev_l1 or rev_l2 or count:\n",
    "            num = 0\n",
    "            if rev_l1:\n",
    "                num += rev_l1.val\n",
    "                rev_l1 = rev_l1.next\n",
    "            if rev_l2:\n",
    "                num += rev_l2.val\n",
    "                rev_l2 = rev_l2.next\n",
    "            count, num = divmod(count + num, 10)\n",
    "            tmo.next = ListNode(num)\n",
    "            tmo = tmo.next\n",
    "        return self.reverseList(ret.next)\n",
    "    \n",
    "\n",
    "    def reverseList(self, head):\n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "\n",
    "        def push_into_stack(lst, stc) :\n",
    "            while lst :\n",
    "                stc.append(lst.val)\n",
    "                lst = lst.next\n",
    "\n",
    "        push_into_stack(l1, stack1)\n",
    "        push_into_stack(l2, stack2)\n",
    "\n",
    "        add = 0\n",
    "        next = None\n",
    "        while len(stack1) and len(stack2) :\n",
    "            sum = stack1.pop() + stack2.pop() + add\n",
    "            cur = ListNode(sum%10, next)\n",
    "            next = cur\n",
    "            add = int(sum / 10)\n",
    "\n",
    "        while len(stack1) :\n",
    "            sum = stack1.pop() + add\n",
    "            cur = ListNode(sum%10, next)\n",
    "            next = cur\n",
    "            add = int(sum / 10)\n",
    "\n",
    "        while len(stack2) :\n",
    "            sum = stack2.pop() + add\n",
    "            cur = ListNode(sum%10, next)\n",
    "            next = cur\n",
    "            add = int(sum / 10)\n",
    "        \n",
    "        if add :\n",
    "            cur = ListNode(add, next)\n",
    "            next = cur\n",
    "        \n",
    "        return next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre, cur = cur, tmp\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        rev_l1 = self.reverseList(l1)\n",
    "        rev_l2 = self.reverseList(l2)\n",
    "        count = 0\n",
    "        ret = ListNode()\n",
    "        tmp = ret\n",
    "        while rev_l1 or rev_l2 or count:\n",
    "            num = 0\n",
    "            if rev_l1:\n",
    "                num += rev_l1.val\n",
    "                rev_l1 = rev_l1.next\n",
    "            if rev_l2:\n",
    "                num += rev_l2.val\n",
    "                rev_l2 = rev_l2.next\n",
    "            count, num = divmod(num + count, 10)\n",
    "            tmp.next = ListNode(num)\n",
    "            tmp = tmp.next\n",
    "        return self.reverseList(ret.next)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        # 第1步：将2个链表变成2个字符串\n",
    "        str1, str2 = '', ''\n",
    "        p1, p2 = l1, l2\n",
    "        while p1:\n",
    "            str1 += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            str2 += str(p2.val)\n",
    "            p2 = p2.next\n",
    "        \n",
    "        # 第2步：将2个字符串变成数字，相加\n",
    "        str3 = str(eval(''.join([str1, '+', str2])))\n",
    "        # str3 = str(int(str1) + int(str2))\n",
    "        \n",
    "        # 第3步：将结果变成链表\n",
    "        pre = None\n",
    "        for i in range(len(str3) - 1, -1, -1):\n",
    "            curnode = ListNode(int(str3[i]))\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        r1 = self.reverseList(l1)\n",
    "        r2 = self.reverseList(l2)\n",
    "        flag = False\n",
    "        prev = ListNode()\n",
    "        ans = prev\n",
    "        while r1 or r2:\n",
    "            if not r1:\n",
    "                r1 = ListNode(0)\n",
    "            if not r2:\n",
    "                r2 = ListNode(0)\n",
    "            temp = r1.val + r2.val + (1 if flag else 0)\n",
    "            flag = temp >= 10\n",
    "            prev.val = temp % 10 if temp >= 10 else temp\n",
    "            r1 = r1.next\n",
    "            r2 = r2.next\n",
    "            prev.next = ListNode()\n",
    "            if not r1 and not r2:\n",
    "                if not flag:\n",
    "                    prev.next = None\n",
    "                else:\n",
    "                    prev.next.val = 1\n",
    "            else:\n",
    "                prev = prev.next\n",
    "        reversed = self.reverseList(ans)\n",
    "        return reversed\n",
    "\n",
    "\n",
    "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        ans = None\n",
    "        current = head\n",
    "        while current:\n",
    "            temp = current.next\n",
    "            current.next = ans\n",
    "            ans = current\n",
    "            current = temp\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def rev(head):\n",
    "            pre = None\n",
    "            cur = head\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = tmp\n",
    "            return pre\n",
    "        l1 = rev(l1)\n",
    "        l2 = rev(l2)\n",
    "        carry = 0\n",
    "        res = ListNode()\n",
    "        cur = res\n",
    "        while l1 or l2 or carry:\n",
    "            tmp = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry = tmp // 10\n",
    "            res.val = tmp % 10\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "            if l1 or l2 or carry:\n",
    "                res.next = ListNode()\n",
    "                res = res.next\n",
    "        return rev(cur)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        rs1 = self.getIntFromListNode(l1)\n",
    "        rs2 = self.getIntFromListNode(l2)\n",
    "        rs = str(rs1 + rs2)\n",
    "        loc = len(rs) -1\n",
    "        n = None\n",
    "        while loc >= 0:\n",
    "            n = ListNode(int(rs[loc]), n)\n",
    "            loc -= 1\n",
    "\n",
    "        return n\n",
    "        \n",
    "    def getIntFromListNode(self, l:ListNode)->int:\n",
    "        rs = 0 \n",
    "        calc_node = l\n",
    "        counter = 10\n",
    "        while calc_node.next!=None:\n",
    "            rs = rs*counter + calc_node.val\n",
    "            calc_node = calc_node.next\n",
    "        rs = rs*counter + calc_node.val\n",
    "        return rs\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def reverse(head):\n",
    "            L = 0\n",
    "            pre = None\n",
    "            while head:\n",
    "                L += 1\n",
    "                next = head.next\n",
    "                head.next = pre\n",
    "                pre = head\n",
    "                head = next\n",
    "            return pre, L\n",
    "\n",
    "        l1, N1 = reverse(l1)\n",
    "        l2, N2 = reverse(l2)\n",
    "\n",
    "        l1, l2 = (l1, l2) if N1 < N2 else (l2, l1)\n",
    "        N1, N2 = (N1, N2) if N1 < N2 else (N2, N1)\n",
    "        c = 0\n",
    "        \n",
    "        ans, tail = l2, l2\n",
    "        while l1:\n",
    "            l2.val += l1.val + c\n",
    "            c = 1 if l2.val >= 10 else 0\n",
    "            l2.val = l2.val%10 if l2.val >= 10 else l2.val\n",
    "            tail = l2\n",
    "            l2 = l2.next\n",
    "            l1 = l1.next\n",
    "\n",
    "        while l2:\n",
    "            l2.val += c\n",
    "            c = 1 if l2.val >= 10 else 0\n",
    "            l2.val = l2.val%10 if l2.val >= 10 else l2.val\n",
    "            tail = l2\n",
    "            l2 = l2.next\n",
    "\n",
    "        if c:\n",
    "            tail.next = ListNode(1)\n",
    "        ans, _ = reverse(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        self.stack_1 = []\n",
    "        self.stack_2 = []\n",
    "        self.stack_3 = []\n",
    "        self.get_val(l1, self.stack_1)\n",
    "        self.get_val(l2, self.stack_2)\n",
    "        return self.generate()\n",
    "    \n",
    "    def get_val(self, list_node, stack):\n",
    "        while list_node:\n",
    "            stack.append(list_node.val)\n",
    "            list_node = list_node.next\n",
    "\n",
    "    def generate(self):\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while self.stack_1 or self.stack_2 or carry:\n",
    "            value_1 = 0 if not self.stack_1 else self.stack_1.pop()\n",
    "            value_2 = 0 if not self.stack_2 else self.stack_2.pop()\n",
    "            cur = value_1 + value_2 + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            currnode = ListNode(cur)\n",
    "            currnode.next = ans\n",
    "            ans = currnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        res1 = []\n",
    "        res2 = []\n",
    "        ll1 = l1\n",
    "        ll2 = l2\n",
    "        while ll1 or ll2:\n",
    "            if ll1:\n",
    "                res1.append(str(ll1.val))\n",
    "                ll1 = ll1.next\n",
    "            if ll2:\n",
    "                res2.append(str(ll2.val))\n",
    "                ll2 = ll2.next\n",
    "\n",
    "        res1 = \"\".join(res1)[::-1]\n",
    "        res2 = \"\".join(res2)[::-1]\n",
    "\n",
    "        res = []\n",
    "        len1 = len(res1)\n",
    "        len2 = len(res2)\n",
    "        i = j = 0\n",
    "        carry = 0\n",
    "        while i < len1 or j < len2:\n",
    "            a = int(res1[i]) if i < len1 else 0\n",
    "            b = int(res2[j]) if j < len2 else 0\n",
    "            ans = a + b + carry\n",
    "            carry = ans // 10\n",
    "            res.append(ListNode(ans % 10))\n",
    "            i += 1\n",
    "            j += 1\n",
    "        if carry:\n",
    "            res.append(ListNode(carry))\n",
    "        res = res[::-1]\n",
    "        for i in range(len(res) - 1):\n",
    "            res[i].next = res[i + 1]\n",
    "        return res[0]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        a = b = None\n",
    "        while l1:\n",
    "            l1.next, a, l1 = a, l1, l1.next\n",
    "        while l2:\n",
    "            l2.next, b, l2 = b, l2, l2.next\n",
    "        result, c = None, 0\n",
    "        while a or b or c:\n",
    "            if a:\n",
    "                c, a = c + a.val, a.next\n",
    "            if b:\n",
    "                c, b = c + b.val, b.next\n",
    "            c, result = c // 10, ListNode(c % 10, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre, cur = cur, tmp\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        rev_l1 = self.reverseList(l1)\n",
    "        rev_l2 = self.reverseList(l2)\n",
    "        count = 0\n",
    "        ret = ListNode()\n",
    "        tmp = ret\n",
    "        while rev_l1 or rev_l2 or count:\n",
    "            num = 0\n",
    "            if rev_l1:\n",
    "                num += rev_l1.val\n",
    "                rev_l1 = rev_l1.next\n",
    "            if rev_l2:\n",
    "                num += rev_l2.val\n",
    "                rev_l2 = rev_l2.next\n",
    "            count, num = divmod(num + count, 10)\n",
    "            tmp.next = ListNode(num)\n",
    "            tmp = tmp.next\n",
    "        return self.reverseList(ret.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        rs1 = self.getIntFromListNode(l1)\n",
    "        rs2 = self.getIntFromListNode(l2)\n",
    "        rs = str(rs1 + rs2)\n",
    "        loc = len(rs) -1\n",
    "        n = None\n",
    "        while loc >= 0:\n",
    "            n = ListNode(int(rs[loc]), n)\n",
    "            loc -= 1\n",
    "\n",
    "        return n\n",
    "        \n",
    "    def getIntFromListNode(self, l:ListNode)->int:\n",
    "        rs = 0 \n",
    "        calc_node = l\n",
    "        counter = 10\n",
    "        while calc_node.next!=None:\n",
    "            rs = rs*counter + calc_node.val\n",
    "            calc_node = calc_node.next\n",
    "        rs = rs*counter + calc_node.val\n",
    "        return rs\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        '''\n",
    "        反转链表 -> 计算 -> 反转链表\n",
    "        '''\n",
    "\n",
    "        def reverse_list(head):\n",
    "            '''翻转链表\n",
    "            '''\n",
    "            if head is None or head.next is None:\n",
    "                return head\n",
    "\n",
    "            slow = head\n",
    "            fast = head.next\n",
    "            while(fast is not None):\n",
    "                tmp = fast.next\n",
    "                fast.next = slow\n",
    "                if slow is head:\n",
    "                    slow.next = None\n",
    "                slow = fast\n",
    "                fast = tmp\n",
    "            return slow\n",
    "\n",
    "        l1 = reverse_list(l1)\n",
    "        l2 = reverse_list(l2)\n",
    "\n",
    "        dummy_head = ListNode()\n",
    "        curr_out = dummy_head\n",
    "        curr1 = l1; curr2 = l2\n",
    "        tmp = 0\n",
    "        while(curr1 is not None or curr2 is not None):\n",
    "            val = 0\n",
    "            if curr1 is not None:\n",
    "                val += curr1.val\n",
    "                curr1 = curr1.next\n",
    "\n",
    "            if curr2 is not None:\n",
    "                val += curr2.val\n",
    "                curr2 = curr2.next\n",
    "\n",
    "            val += tmp\n",
    "            curr_out.next = ListNode(val % 10)\n",
    "            curr_out = curr_out.next\n",
    "            tmp = val // 10\n",
    "\n",
    "        if tmp:\n",
    "            curr_out.next = ListNode(tmp)\n",
    "\n",
    "        rst = dummy_head.next\n",
    "        rst = reverse_list(rst)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry > 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            total = a + b + carry\n",
    "            carry = total // 10\n",
    "            total = total % 10\n",
    "            curnode = ListNode(total)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\"\"\"\n",
    "方法1栈的思维\n",
    "\"\"\"\n",
    "# class Solution:\n",
    "#     def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "#         a = []\n",
    "#         b = []\n",
    "#         while l1:\n",
    "#             a.append(l1.val)\n",
    "#             l1 = l1.next\n",
    "\n",
    "#         while l2:\n",
    "#             b.append(l2.val)\n",
    "#             l2 = l2.next\n",
    "#         r = None\n",
    "#         carry = 0\n",
    "#         while a or b or carry:\n",
    "#             x = a.pop(-1) if a else 0\n",
    "#             y = b.pop(-1) if b else 0\n",
    "#             carry, cur_val = divmod(x+y+carry, 10)\n",
    "\n",
    "#             cur = ListNode(cur_val)\n",
    "#             cur.next = r\n",
    "#             r = cur\n",
    "\n",
    "#         return r\n",
    "\"\"\"\n",
    "方法2反转链表的思维\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        pre = q = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            q = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = q\n",
    "        \n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        r_l1 = self.reverseList(l1)\n",
    "        r_l2 = self.reverseList(l2)\n",
    "        carry = 0\n",
    "        result = None\n",
    "        while r_l1 or r_l2 or carry:\n",
    "            num = 0\n",
    "            if r_l1:\n",
    "                num += r_l1.val\n",
    "                r_l1 = r_l1.next\n",
    "            if r_l2:\n",
    "                num += r_l2.val\n",
    "                r_l2 = r_l2.next\n",
    "            carry, cur_val = divmod(num + carry, 10)\n",
    "            cur_node = ListNode(cur_val)\n",
    "            cur_node.next = result\n",
    "            result = cur_node\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverse(self,head):\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        last= self.reverse(head.next)\n",
    "        head.next.next=  head\n",
    "        head.next=  None\n",
    "        return last\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverse(l1)\n",
    "        l2 = self.reverse(l2)\n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        step = 0\n",
    "        while l1 or l2 or step:\n",
    "            cur = step\n",
    "            if l1:\n",
    "                cur+=l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                cur+=l2.val\n",
    "                l2 = l2.next\n",
    "            step,a = divmod(cur,10)\n",
    "            p.next= ListNode(a,None)\n",
    "            p = p.next\n",
    "        p = self.reverse(dummy.next)\n",
    "        return p \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        num1, num2 = 0, 0\n",
    "        cur = l1\n",
    "        while cur:\n",
    "            num1 = num1 * 10 + cur.val\n",
    "            cur = cur.next\n",
    "        cur = l2\n",
    "        while cur:\n",
    "            num2 = num2 * 10 + cur.val\n",
    "            cur = cur.next\n",
    "        res = num1 + num2\n",
    "        cur = ListNode(res % 10)\n",
    "        res = res // 10\n",
    "        while res:\n",
    "            p = ListNode(res % 10)\n",
    "            res = res // 10\n",
    "            p.next = cur\n",
    "            cur = p\n",
    "        return cur\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1,s2=[],[]\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1=l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans =None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a+b+carry\n",
    "            carry  = cur//10\n",
    "            cur %= 10\n",
    "            node = ListNode(cur)\n",
    "            node.next =ans \n",
    "            ans =node\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stk1, stk2 = [], []\n",
    "        while l1:\n",
    "            stk1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stk2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        last = None\n",
    "        carry = 0\n",
    "        while stk1 or stk2 or carry:\n",
    "            if stk1:\n",
    "                carry += stk1.pop()\n",
    "            if stk2:\n",
    "                carry += stk2.pop()\n",
    "            node = ListNode(carry % 10, last)\n",
    "            last = node\n",
    "            carry //= 10\n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\"\"\"\n",
    "方法1栈的思维\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        a = []\n",
    "        b = []\n",
    "        while l1:\n",
    "            a.append(l1.val)\n",
    "            l1 = l1.next\n",
    "\n",
    "        while l2:\n",
    "            b.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        r = None\n",
    "        carry = 0\n",
    "        while a or b or carry:\n",
    "            x = a.pop(-1) if a else 0\n",
    "            y = b.pop(-1) if b else 0\n",
    "            carry, cur_val = divmod(x+y+carry, 10)\n",
    "\n",
    "            cur = ListNode(cur_val)\n",
    "            cur.next = r\n",
    "            r = cur\n",
    "\n",
    "        return r\n",
    "\"\"\"\n",
    "方法2反转链表的思维\n",
    "\"\"\"\n",
    "# class Solution:\n",
    "#     def reverseList(self, head):\n",
    "#         pre = q = None\n",
    "#         cur = head\n",
    "#         while cur:\n",
    "#             q = cur.next\n",
    "#             cur.next = pre\n",
    "#             pre = cur\n",
    "#             cur = q\n",
    "        \n",
    "#         return pre\n",
    "\n",
    "#     def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "#         r_l1 = self.reverseList(l1)\n",
    "#         r_l2 = self.reverseList(l2)\n",
    "#         carry = 0\n",
    "#         result = None\n",
    "#         while r_l1 or r_l2 or carry:\n",
    "#             num = 0\n",
    "#             if r_l1:\n",
    "#                 num += r_l1.val\n",
    "#                 r_l1 = r_l1.next\n",
    "#             if r_l2:\n",
    "#                 num += r_l2.val\n",
    "#                 r_l2 = r_l2.next\n",
    "#             carry, cur_val = divmod(num + carry, 10)\n",
    "#             cur_node = ListNode(cur_val)\n",
    "#             cur_node.next = result\n",
    "#             result = cur_node\n",
    "#         return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1=[]\n",
    "        stack2=[]\n",
    "\n",
    "        tmp=l1\n",
    "        while tmp:\n",
    "            stack1.append(tmp.val)\n",
    "            tmp=tmp.next\n",
    "        tmp=l2\n",
    "        while tmp:\n",
    "            stack2.append(tmp.val)\n",
    "            tmp=tmp.next\n",
    "\n",
    "        num3=0\n",
    "        head=None\n",
    "        while stack1 or stack2:\n",
    "            num1=0\n",
    "            if stack1:\n",
    "                num1=stack1.pop()\n",
    "            num2=0\n",
    "            if stack2:\n",
    "                num2=stack2.pop()\n",
    "            sumv=num1+num2+num3\n",
    "            if sumv>=10:\n",
    "                num3=1\n",
    "            else:\n",
    "                num3=0\n",
    "            \n",
    "            newnode=ListNode(sumv%10,head)\n",
    "            head=newnode\n",
    "        if num3:\n",
    "            newnode=ListNode(num3,head)\n",
    "            head=newnode\n",
    "        return head\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode):\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(str(l1.val))\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(str(l2.val))\n",
    "            l2 = l2.next\n",
    "        n1 = ''.join(s1)\n",
    "        n2 = ''.join(s2)\n",
    "        s = str(int(n1) + int(n2))\n",
    "        res = p = ListNode(0)\n",
    "        for i in s:\n",
    "            p.next = ListNode(int(i))\n",
    "            p = p.next\n",
    "        return res.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)\n",
    "        return self.reverseList(self.addTwoListNum(l1, l2))\n",
    "\n",
    "    def reverseList(self, l):\n",
    "        if not l or not l.next:\n",
    "            return l\n",
    "        prev, curr = None, l\n",
    "        while curr:\n",
    "            curr.next, curr, prev = prev, curr.next, curr\n",
    "        return prev\n",
    "\n",
    "    def addTwoListNum(self, l1, l2):\n",
    "        carry = 0\n",
    "        dummy1, prev1, prev2 = ListNode(), ListNode(), ListNode\n",
    "        dummy1.next, prev1.next, prev2.next = l1, l1, l2\n",
    "        while l1 or l2:\n",
    "            if l1 and l2:\n",
    "                # divmod\n",
    "                carry, l1.val = divmod(l1.val+l2.val+carry, 10)\n",
    "                l1, l2, prev1, prev2 = l1.next, l2.next, l1, l2\n",
    "            elif not l1:\n",
    "                l1, prev1.next = l2, l2\n",
    "                # 注意\n",
    "                l2 = None\n",
    "            else:\n",
    "                carry, l1.val = divmod(l1.val+carry, 10)\n",
    "                l1, prev1 = l1.next, l1\n",
    "        # 注意\n",
    "        if carry:\n",
    "            node = ListNode(carry)\n",
    "            prev1.next = node\n",
    "        return dummy1.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1s = []\n",
    "        l2s = []\n",
    "        tree = l1\n",
    "        while l1:\n",
    "            l1s.append(l1)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            l2s.append(l2)\n",
    "            l2 = l2.next\n",
    "        reminder = 0\n",
    "        while l1s and l2s:\n",
    "            cur1 = l1s.pop()\n",
    "            cur2 = l2s.pop()\n",
    "            cur1.val = cur1.val +cur2.val + reminder\n",
    "            reminder = cur1.val//10\n",
    "            cur1.val = cur1.val%10\n",
    "        while reminder or l1s or l2s:\n",
    "            if not l2s and not l1s:\n",
    "                cur = ListNode(reminder)\n",
    "                cur.next = tree\n",
    "                tree = cur\n",
    "                reminder = 0\n",
    "            elif not l2s:\n",
    "                cur = l1s.pop()\n",
    "                cur.val = cur.val+reminder\n",
    "                reminder = cur.val//10\n",
    "                cur.val = cur.val%10\n",
    "            elif not l1s:\n",
    "                cur = l2s.pop()\n",
    "                cur.val = cur.val+reminder\n",
    "                reminder = cur.val//10\n",
    "                cur.val = cur.val%10 \n",
    "                cur.next = tree\n",
    "                tree = cur\n",
    "        return tree        \n",
    "                \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        # 黄狂俄国非空链表翻转\n",
    "        head1 = self.reverse(l1)\n",
    "        head2 = self.reverse(l2)\n",
    "        # 接下来相加\n",
    "        jinwei = 0\n",
    "        dummy = ListNode(val=-1)\n",
    "        cur = dummy\n",
    "        while head1 or head2:\n",
    "            if head1:\n",
    "                num1 = head1.val\n",
    "                head1 = head1.next\n",
    "            else:\n",
    "                num1 = 0\n",
    "            if head2:\n",
    "                num2 = head2.val\n",
    "                head2 = head2.next\n",
    "            else:\n",
    "                num2 = 0\n",
    "            res_temp = (num1+num2+jinwei)%10\n",
    "            jinwei = (num1+num2+jinwei)//10\n",
    "            cur.next = ListNode(val=res_temp)\n",
    "            cur = cur.next\n",
    "        if jinwei==1:\n",
    "            cur.next = ListNode(val=jinwei)\n",
    "        \n",
    "        # 相加后再翻转\n",
    "        temp = dummy.next\n",
    "        dummy.next = None\n",
    "        res = self.reverse(temp)\n",
    "        return (res)\n",
    "\n",
    "\n",
    "\n",
    "    def reverse(self, node):\n",
    "        prev = None\n",
    "        cur = node\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = prev\n",
    "            prev = cur\n",
    "            cur = nxt\n",
    "        return prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reversal(l):\n",
    "            cur = l\n",
    "            pre = None\n",
    "            while cur:\n",
    "                t = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = t\n",
    "            return pre\n",
    "        l1 = reversal(l1)\n",
    "        l2 = reversal(l2)\n",
    "        head = ListNode()\n",
    "        p = head\n",
    "        jw = 0\n",
    "        while l1 or l2:\n",
    "            p.next = ListNode((l1.val if l1 else 0) + (l2.val if l2 else 0) + jw)\n",
    "            p = p.next\n",
    "            jw = 0\n",
    "            if p.val >= 10:\n",
    "                p.val %= 10\n",
    "                jw = 1\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "        if jw:\n",
    "            p.next = ListNode(1)\n",
    "        return reversal(head.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1 = []\n",
    "        s2 = []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry = 0\n",
    "        ans = None\n",
    "        while s1 or s2 or carry:\n",
    "            a = s1.pop() if s1 else 0\n",
    "            b = s2.pop() if s2 else 0\n",
    "            carry = a + b + carry\n",
    "            val = carry % 10\n",
    "            carry = carry // 10\n",
    "            node = ListNode(val)\n",
    "            node.next = ans\n",
    "            ans = node\n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "\n",
    "        def reverseList(head:ListNode)->ListNode:\n",
    "            prev = None\n",
    "            cur = head\n",
    "            while cur:\n",
    "                next = cur.next\n",
    "                cur.next =  prev\n",
    "                prev = cur\n",
    "                cur = next \n",
    "            return  prev\n",
    "\n",
    "        head1 = reverseList(l1)\n",
    "        head2 = reverseList(l2)\n",
    "\n",
    "\n",
    "        def addReverseList(head1:ListNode,head2:ListNode)->ListNode:\n",
    "            dumpy =  ListNode(0)\n",
    "            sumNode = dumpy\n",
    "            carray = 0\n",
    "            while  head1 or  head2:\n",
    "                sumNum =   (0 if head1 is None else  head1.val) + (0 if head2 is None else  head2.val) + carray\n",
    "                carray =  sumNum//10\n",
    "                newNode = ListNode(sumNum%10)\n",
    "                sumNode.next = newNode\n",
    "                sumNode = sumNode.next\n",
    "                head1 = None if head1 is None else head1.next\n",
    "                head2 = None if head2 is None else head2.next\n",
    "            \n",
    "            if  carray ==1:\n",
    "                sumNode.next =  ListNode(1)\n",
    "\n",
    "            return dumpy.next\n",
    "\n",
    "        node = addReverseList(head1,head2)\n",
    "        return reverseList(node)\n",
    "        \n",
    " \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reversed(self, heap: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        pre = None\n",
    "        cur = heap\n",
    "        while cur:\n",
    "            next = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = next\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        cur = dummy = ListNode()\n",
    "        carry = 0\n",
    "        l1=self.reversed(l1)\n",
    "        l2=self.reversed(l2)\n",
    "        while l1 or l2 or carry:\n",
    "            carry = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            cur.next = ListNode(carry % 10)\n",
    "            carry = carry // 10\n",
    "            cur = cur.next\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        return self.reversed(dummy.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse_node(head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "            cur = head\n",
    "            prev = None\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = prev\n",
    "                prev = cur\n",
    "                cur = nxt\n",
    "            return prev\n",
    "        l1, l2 = reverse_node(l1), reverse_node(l2)\n",
    "        \n",
    "        carry = 0\n",
    "        cur = dummy = ListNode()\n",
    "        while l1 or l2 or carry:\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            cur.next = ListNode(carry % 10)\n",
    "            cur = cur.next\n",
    "            carry //= 10\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        dummy.next = reverse_node(dummy.next)\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "\n",
    "import itertools\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        num1 = []\n",
    "        num2 = []\n",
    "\n",
    "        while l1:\n",
    "            num1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "\n",
    "        while l2:\n",
    "            num2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "\n",
    "        res = [0] * (max(len(num1), len(num2)) + 1)\n",
    "        node = None\n",
    "\n",
    "        for i, (n1, n2) in enumerate(itertools.zip_longest(reversed(num1), reversed(num2), fillvalue=0)):\n",
    "            curr_sum = res[i] + n1 + n2\n",
    "\n",
    "            res[i] = curr_sum % 10\n",
    "            res[i + 1] = curr_sum // 10\n",
    "\n",
    "            curr_node = ListNode(res[i])\n",
    "            curr_node.next = node\n",
    "\n",
    "            node = curr_node\n",
    "\n",
    "        if res[-1]:\n",
    "            curr_node = ListNode(res[-1])\n",
    "            curr_node.next = node\n",
    "\n",
    "            node = curr_node\n",
    "\n",
    "        return node\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry, p = 0, None\n",
    "        while s1 or s2 or carry:\n",
    "            num1 = s1.pop() if s1 else 0\n",
    "            num2 = s2.pop() if s2 else 0\n",
    "            ans = num1 + num2 + carry\n",
    "            carry = ans // 10\n",
    "            ans %= 10\n",
    "            p = ListNode(ans, p)\n",
    "        return p\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l2 is None or l1 is None:\n",
    "            return l1 if l1 else l2\n",
    "        l1, l2 = self.reverse(l1), self.reverse(l2)\n",
    "        # carry = ListNode(0)\n",
    "        p1, p2 = ListNode(), ListNode()\n",
    "        p1, p2 = l1, l2\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        carry = 0\n",
    "        while p1 or p2:\n",
    "            carry += (p1.val if p1 else 0) + (p2.val if p2 else 0)\n",
    "            cur.next = ListNode(carry%10)\n",
    "            carry = carry // 10\n",
    "            cur = cur.next\n",
    "            if(p1): p1 = p1.next\n",
    "            if(p2): p2 = p2.next\n",
    "        if carry:\n",
    "            cur.next = ListNode(carry)\n",
    "        return self.reverse(dummy.next)\n",
    "        \n",
    "    def reverse(self, head):\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        pre, cur, las = ListNode(), ListNode(), ListNode()\n",
    "        pre, cur, las = None, head, head.next\n",
    "        while cur:\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = las\n",
    "            if las: las = las.next\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        a = b = 0\n",
    "        cur1, cur2 = l1, l2\n",
    "        while cur1 or cur2:\n",
    "            if cur1:\n",
    "                a = a*10+cur1.val\n",
    "                cur1 = cur1.next\n",
    "            if cur2:\n",
    "                b = b*10+cur2.val\n",
    "                cur2 = cur2.next\n",
    "        c = a+b\n",
    "        dummy_head = ListNode()\n",
    "        while c:\n",
    "            dummy_head.next = ListNode(c % 10, dummy_head.next)\n",
    "            c //= 10\n",
    "        return dummy_head.next if dummy_head.next else dummy_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        num1, num2 = self.transList2Num(l1), self.transList2Num(l2)\n",
    "\n",
    "        sum_num = num1 + num2\n",
    "\n",
    "        return self.transNum2List(sum_num)\n",
    "    \n",
    "    def transNum2List(self, num):\n",
    "        dummyNode = ListNode(0)\n",
    "\n",
    "        while num or dummyNode.next is None:\n",
    "            mod = num % 10\n",
    "            cur_node = ListNode(mod)\n",
    "            cur_node.next = dummyNode.next\n",
    "            dummyNode.next = cur_node\n",
    "\n",
    "            num = num // 10\n",
    "        \n",
    "        return dummyNode.next\n",
    "\n",
    "    def transList2Num(self, head):\n",
    "        res = 0\n",
    "\n",
    "        while head:\n",
    "            res = res * 10 + head.val\n",
    "            head = head.next\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def list2num(head: ListNode) -> int:\n",
    "            num = 0\n",
    "            node = head\n",
    "            while node != None:\n",
    "                num = num * 10 + node.val\n",
    "                node = node.next\n",
    "            return num\n",
    "        \n",
    "        def num2list(num: int) -> ListNode:\n",
    "            _num = num\n",
    "            last = None\n",
    "            if num != 0:\n",
    "                while _num > 0:\n",
    "                    v = _num % 10\n",
    "                    _num //= 10\n",
    "                    node = ListNode(val=v, next=last)\n",
    "                    last = node\n",
    "            else:\n",
    "                last = ListNode(val=0)\n",
    "            return last\n",
    "        \n",
    "        num = list2num(l1)\n",
    "        num += list2num(l2)\n",
    "        node = num2list(num)\n",
    "\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        list1=[]\n",
    "        list2=[]\n",
    "        while l1 or l2:\n",
    "            if l1:\n",
    "                list1.append(l1.val)\n",
    "                l1=l1.next\n",
    "            if l2:\n",
    "                list2.append(l2.val)\n",
    "                l2=l2.next\n",
    "        flag=0\n",
    "        dummy=ListNode()\n",
    "        while list1 or list2:\n",
    "            num1=list1.pop() if list1 else 0\n",
    "            num2=list2.pop() if list2 else 0\n",
    "            cnt=(num1+num2+flag)%10\n",
    "            flag=(num1+num2+flag)//10\n",
    "            p=ListNode(cnt)\n",
    "            p.next=dummy.next\n",
    "            dummy.next=p\n",
    "        if flag==1:\n",
    "            p=ListNode(1)\n",
    "            p.next=dummy.next\n",
    "            dummy.next=p\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:       \n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverseListNode(l1)\n",
    "        l2 = self.reverseListNode(l2)\n",
    "\n",
    "        dummy_head = ListNode()\n",
    "        cur = dummy_head\n",
    "        carry = 0\n",
    "        while l1 or l2:\n",
    "            val1 = l1.val if l1 else 0\n",
    "            val2 = l2.val if l2 else 0\n",
    "            tmp = val1+val2+carry\n",
    "            cur.next = ListNode(tmp%10)\n",
    "            carry = tmp//10\n",
    "\n",
    "            l1 = l1.next if l1 else l1\n",
    "            l2 = l2.next if l2 else l2\n",
    "            cur = cur.next\n",
    "        \n",
    "        if carry:\n",
    "            cur.next = ListNode(carry)\n",
    "        \n",
    "        return self.reverseListNode(dummy_head.next) \n",
    "\n",
    "\n",
    "    def reverseListNode(self, l:ListNode):\n",
    "        if not l:\n",
    "            return l\n",
    "        pre, cur = None, l\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "    \n",
    "        return pre\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        rs1 = self.getIntFromListNode(l1)\n",
    "        rs2 = self.getIntFromListNode(l2)\n",
    "        print(rs2)\n",
    "        carry = 0\n",
    "        n = None\n",
    "        while len(rs1) > 0 and len(rs2) > 0:\n",
    "            a = rs1.pop()\n",
    "            b = rs2.pop()\n",
    "            s = a + b + carry\n",
    "            if s >= 10:\n",
    "                s = s% 10\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            n = ListNode(val=s, next=n)\n",
    "        while len(rs1) > 0:\n",
    "            a = rs1.pop()\n",
    "            s = a+carry\n",
    "            if s >= 10:\n",
    "                s = s% 10\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            n = ListNode(val=s, next=n)\n",
    "        while len(rs2) > 0:\n",
    "            a = rs2.pop()\n",
    "            s = a+carry\n",
    "            if s >= 10:\n",
    "                s = s% 10\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            n = ListNode(val=s, next=n)\n",
    "        if carry == 1:\n",
    "            n = ListNode(val=1, next=n)\n",
    "        return n\n",
    "        \n",
    "    def getIntFromListNode(self, l:ListNode)->list[int]:\n",
    "        rs = []\n",
    "        calc_node = l\n",
    "        while calc_node.next!=None:\n",
    "            rs.append(calc_node.val)\n",
    "            calc_node = calc_node.next\n",
    "        rs.append(calc_node.val)\n",
    "        return rs\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def reverse(head):\n",
    "            cur = head\n",
    "            pre = None\n",
    "            while cur:\n",
    "                nt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur \n",
    "                cur = nt\n",
    "            return pre\n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        carry = 0\n",
    "        cur = ans = ListNode()\n",
    "        while carry or l1 or l2 :\n",
    "            val = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            carry,val = divmod(val,10)\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "            l1 = l1.next if l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "        return reverse(ans.next)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        a = 0\n",
    "        p = l1\n",
    "        while p:\n",
    "            a = a*10+p.val\n",
    "            p = p.next\n",
    "        b = 0\n",
    "        p = l2\n",
    "        while p:\n",
    "            b = b*10+p.val\n",
    "            p = p.next\n",
    "\n",
    "        c = a + b\n",
    "        nums = []\n",
    "        if c:        \n",
    "            while c:\n",
    "                nums.insert(0,c%10)\n",
    "                c //= 10\n",
    "        else:\n",
    "            nums.append(0)\n",
    "        \n",
    "        ans = ListNode()\n",
    "        p = ans\n",
    "        idx,n= 0,len(nums)\n",
    "        while True:\n",
    "            # print(idx)\n",
    "            p.val = nums[idx]\n",
    "            # ans.insert(0,c%10)\n",
    "            idx += 1\n",
    "            if idx < n:\n",
    "                p.next = ListNode()\n",
    "                p = p.next\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if len(s1) == 0 else s1.pop()\n",
    "            b = 0 if len(s2) == 0 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverselistnode(self,phead):\n",
    "        if phead == None:\n",
    "            return phead\n",
    "        pre,cur = None,phead\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre\n",
    "        \n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l1 == None:return l2\n",
    "        if l2 == None:return l1\n",
    "        rev_l1 = self.reverselistnode(l1)\n",
    "        rev_l2 = self.reverselistnode(l2)\n",
    "        carry = 0\n",
    "        dummy = ListNode(val = 0)\n",
    "        current = dummy\n",
    "        while rev_l1 or rev_l2 or carry:\n",
    "            val1 = 0 if rev_l1 == None else rev_l1.val\n",
    "            val2 = 0 if rev_l2 == None else rev_l2.val\n",
    "            temp = val1+val2+carry\n",
    "            carry,temp = divmod(temp,10)\n",
    "            current.next = ListNode(temp)\n",
    "            current = current.next\n",
    "            if rev_l1:\n",
    "                rev_l1 = rev_l1.next\n",
    "            if rev_l2:\n",
    "                rev_l2 = rev_l2.next\n",
    "        return self.reverselistnode(dummy.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode):\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(str(l1.val))\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(str(l2.val))\n",
    "            l2 = l2.next\n",
    "        n1 = ''.join(s1)\n",
    "        n2 = ''.join(s2)\n",
    "        s = str(int(n1) + int(n2))\n",
    "        res = p = ListNode(0)\n",
    "        for i in s:\n",
    "            p.next = ListNode(int(i))\n",
    "            p = p.next\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = 0, 0\n",
    "        while l1:\n",
    "            s1 = s1*10 + l1.val\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2 = s2*10 + l2.val\n",
    "            l2 = l2.next\n",
    "        s = s1 + s2\n",
    "        if s == 0:\n",
    "            return ListNode(0)\n",
    "        res = ListNode()\n",
    "        load = res\n",
    "        loads = []\n",
    "        while s >0:\n",
    "            loads.append(s%10)\n",
    "            s //= 10\n",
    "        loads.reverse()\n",
    "        for v in loads:\n",
    "            tmp = ListNode(v)\n",
    "            load.next = tmp\n",
    "            load = tmp\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        nums1 = self.get_nums(l1)\n",
    "        nums2 = self.get_nums(l2)\n",
    "        result = [0] * (max(len(nums1), len(nums2)) + 1)\n",
    "        i1, i2, i3 = len(nums1) - 1, len(nums2) - 1, len(result) - 1\n",
    "        while i1 >= 0 or i2 >= 0:\n",
    "            if i1 >= 0:\n",
    "                result[i3] += nums1[i1]\n",
    "                i1 -= 1\n",
    "            if i2 >= 0:\n",
    "                result[i3] += nums2[i2]\n",
    "                i2 -= 1\n",
    "            i3 -= 1\n",
    "        for i in range(len(result) - 1, 0, -1):\n",
    "            if result[i] >= 10:\n",
    "                result[i - 1] += result[i] // 10\n",
    "                result[i] %= 10\n",
    "        start = 0 if result[0] > 0 else 1\n",
    "        head = ListNode(result[start])\n",
    "        temp = head\n",
    "        for i in range(start + 1, len(result)):\n",
    "            temp.next = ListNode(result[i])\n",
    "            temp = temp.next\n",
    "        return head\n",
    "\n",
    "    def get_nums(self, head: Optional[ListNode]) -> List[int]:\n",
    "        nums = []\n",
    "        temp = head\n",
    "        while temp is not None:\n",
    "            nums.append(temp.val)\n",
    "            temp = temp.next\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry, p = 0, None\n",
    "        while s1 or s2 or carry:\n",
    "            num1 = s1.pop() if s1 else 0\n",
    "            num2 = s2.pop() if s2 else 0\n",
    "            ans = num1 + num2 + carry\n",
    "            carry = ans // 10\n",
    "            ans %= 10\n",
    "            p = ListNode(ans, p)\n",
    "        return p\n",
    "     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse_node(head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "            cur = head\n",
    "            prev = None\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = prev\n",
    "                prev = cur\n",
    "                cur = nxt\n",
    "            return prev\n",
    "        l1, l2 = reverse_node(l1), reverse_node(l2)\n",
    "        \n",
    "        carry = 0\n",
    "        cur = dummy = ListNode()\n",
    "        while l1 or l2 or carry:\n",
    "            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)\n",
    "            cur.next = ListNode(carry % 10)\n",
    "            cur = cur.next\n",
    "            carry //= 10\n",
    "            if l1: l1 = l1.next\n",
    "            if l2: l2 = l2.next\n",
    "        dummy.next = reverse_node(dummy.next)\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        str1, str2 = '', ''\n",
    "        p1, p2 = l1, l2\n",
    "        while p1:\n",
    "            str1 += str(p1.val)\n",
    "            p1 = p1.next\n",
    "        while p2:\n",
    "            str2 += str(p2.val)\n",
    "            p2 = p2.next\n",
    "        ret = str(int(str1) + int(str2))\n",
    "        pre = None\n",
    "        for i in range(len(ret) - 1, -1, -1):\n",
    "            curnode = ListNode(int(ret[i]))\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverseList(l1)\n",
    "        l2 = self.reverseList(l2)\n",
    "        return self.reverseList(self.addTwoListNum(l1, l2))\n",
    "\n",
    "    def reverseList(self, l):\n",
    "        if not l or not l.next:\n",
    "            return l\n",
    "        prev, curr = None, l\n",
    "        while curr:\n",
    "            curr.next, curr, prev = prev, curr.next, curr\n",
    "        return prev\n",
    "\n",
    "    def addTwoListNum(self, l1, l2):\n",
    "        carry = 0\n",
    "        dummy1, prev1, prev2 = ListNode(), ListNode(), ListNode\n",
    "        dummy1.next, prev1.next, prev2.next = l1, l1, l2\n",
    "        while l1 or l2:\n",
    "            if l1 and l2:\n",
    "                carry, l1.val = divmod(l1.val+l2.val+carry, 10)\n",
    "                l1, l2, prev1, prev2 = l1.next, l2.next, l1, l2\n",
    "            elif not l1:\n",
    "                l1, prev1.next = l2, l2\n",
    "                l2 = None\n",
    "            else:\n",
    "                carry, l1.val = divmod(l1.val+carry, 10)\n",
    "                l1, prev1 = l1.next, l1\n",
    "        if carry:\n",
    "            node = ListNode(carry)\n",
    "            prev1.next = node\n",
    "        return dummy1.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def func(head):\n",
    "            cur = head\n",
    "            s = ''\n",
    "            while cur:\n",
    "                s += str(cur.val)\n",
    "                cur = cur.next\n",
    "            return s \n",
    "        s1 = func(l1)\n",
    "        s2 = func(l2)\n",
    "        n = str(int(s1)+int(s2))\n",
    "        cur = ans = ListNode()\n",
    "        for i in n:\n",
    "            cur.next = ListNode(int(i))\n",
    "            cur = cur.next\n",
    "        return ans.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def reverse(head) -> ListNode:\n",
    "            pre, cur = None, head\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = nxt\n",
    "            return pre\n",
    "        \n",
    "        def addTwo(l1, l2) -> ListNode:\n",
    "            cur = dummy = ListNode()\n",
    "            carry = 0\n",
    "            while l1 or l2 or carry:\n",
    "                if l1:\n",
    "                    carry += l1.val\n",
    "                    l1 = l1.next\n",
    "                if l2:\n",
    "                    carry += l2.val\n",
    "                    l2 = l2.next\n",
    "                cur.next = ListNode(carry % 10)\n",
    "                carry //= 10\n",
    "                cur = cur.next\n",
    "            return dummy.next\n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        l3 = addTwo(l1,l2)\n",
    "        return reverse(l3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "\n",
    "        def tranverse(l):\n",
    "            sum_res = 0\n",
    "\n",
    "            while l is not None:\n",
    "                temp = l.val\n",
    "                sum_res = sum_res * 10 + temp\n",
    "                l = l.next \n",
    "            return sum_res\n",
    "\n",
    "        l1_sum = tranverse(l1)\n",
    "\n",
    "        print(l1_sum)\n",
    "        l2_sum = tranverse(l2)\n",
    "        print(l2_sum)\n",
    "\n",
    "        total_sum = str(l1_sum + l2_sum)\n",
    "        print(total_sum)\n",
    "\n",
    "        pre_head = ListNode()\n",
    "        cur = pre_head\n",
    "\n",
    "        while total_sum:\n",
    "            node = ListNode(int(total_sum[0]))\n",
    "            total_sum = total_sum[1:]\n",
    "            cur.next = node\n",
    "            cur = node\n",
    "\n",
    "        return pre_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        rs1 = self.getIntFromListNode(l1)\n",
    "        rs2 = self.getIntFromListNode(l2)\n",
    "        rs = str(rs1 + rs2)\n",
    "        loc = len(rs) -1\n",
    "        n = None\n",
    "        while loc >= 0:\n",
    "            n = ListNode(int(rs[loc]), n)\n",
    "            loc -= 1\n",
    "\n",
    "        return n\n",
    "        \n",
    "    def getIntFromListNode(self, l:ListNode)->int:\n",
    "        rs = 0 \n",
    "        calc_node = l\n",
    "        counter = 10\n",
    "        while calc_node.next!=None:\n",
    "            rs = rs*counter + calc_node.val\n",
    "            calc_node = calc_node.next\n",
    "        rs = rs*counter + calc_node.val\n",
    "        return rs\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1 and not l2:\n",
    "            return \n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "        def getNum(l):\n",
    "            num=0\n",
    "            while l:\n",
    "                num=10*num+l.val\n",
    "                l=l.next\n",
    "            return num\n",
    "        num=getNum(l1)+getNum(l2)\n",
    "        print(num)\n",
    "        node=None\n",
    "        for i in str(num)[::-1]:\n",
    "            #print(i)\n",
    "            node=ListNode(int(i),node)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        carry = 0\n",
    "        dummy = ListNode(-1)\n",
    "        while stack1 or stack2 or carry:\n",
    "            tmp_sum = carry\n",
    "            if stack1:\n",
    "                tmp_sum += stack1.pop()\n",
    "            if stack2:\n",
    "                tmp_sum += stack2.pop()\n",
    "            carry = tmp_sum // 10\n",
    "            node = ListNode(tmp_sum % 10)\n",
    "            node.next = dummy.next\n",
    "            dummy.next = node\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        while l1:\n",
    "            stack1.append(l1)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2)\n",
    "            l2 = l2.next\n",
    "        carry = 0\n",
    "        nxt = None\n",
    "        res = None\n",
    "        while stack1 or stack2:\n",
    "            if stack1:\n",
    "                t1 = stack1.pop().val\n",
    "            else:\n",
    "                t1 = 0\n",
    "            if stack2:\n",
    "                t2 = stack2.pop().val\n",
    "            else:\n",
    "                t2 = 0\n",
    "            res = ListNode((t1 + t2 + carry) % 10)\n",
    "            carry = 1 if (t1 + t2 + carry) >= 10 else 0\n",
    "            res.next = nxt\n",
    "            nxt = res\n",
    "        if carry:\n",
    "            res = ListNode(next=res, val=1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        def reverse(cur):\n",
    "            pre = None\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = nxt\n",
    "            return pre\n",
    "\n",
    "        l1, l2 = reverse(l1), reverse(l2)\n",
    "        carry = 0\n",
    "        dummy = ListNode(-1)\n",
    "        cur = dummy\n",
    "        while l1 or l2 or carry:\n",
    "            x, y = 0, 0\n",
    "            if l1:\n",
    "                x = l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                y = l2.val\n",
    "                l2 = l2.next\n",
    "            s = x + y + carry\n",
    "            ans = ListNode(s % 10)\n",
    "            cur.next = ans\n",
    "            cur = cur.next\n",
    "            carry = s // 10\n",
    "        return reverse(dummy.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry:\n",
    "            a1 = 0 if not s1 else s1.pop()\n",
    "            b1 = 0 if not s2 else s2.pop()\n",
    "            carry = a1 + b1 + carry\n",
    "            cur = carry % 10\n",
    "            carry //= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1 or l1.val == 0:\n",
    "            return l2\n",
    "        \n",
    "        if not l2 or l2.val == 0:\n",
    "            return l1\n",
    "        \n",
    "        buf1 = []\n",
    "        buf2 = []\n",
    "\n",
    "        m = 0\n",
    "        n = 0\n",
    "\n",
    "        while l1:\n",
    "            buf1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "            m += 1\n",
    "\n",
    "        while l2:\n",
    "            buf2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "            n += 1\n",
    "\n",
    "        if m < n:\n",
    "            buf1 = [0] * (n - m) + buf1\n",
    "        elif m > n:\n",
    "            buf2 = [0] * (m - n) + buf2\n",
    "\n",
    "        print(buf1)\n",
    "        print(buf2)\n",
    "\n",
    "        tmp = buf1.pop() + buf2.pop()\n",
    "        one = False\n",
    "        if tmp >= 10:\n",
    "            tail = ListNode(val=tmp%10)\n",
    "            one = True\n",
    "        else:\n",
    "            tail = ListNode(val=tmp)\n",
    "\n",
    "        for i in range(max(m, n)-1):\n",
    "            tmp = buf1.pop() + buf2.pop()\n",
    "\n",
    "            if one:\n",
    "                tmp += 1\n",
    "                one = False\n",
    "            \n",
    "            if tmp >= 10:\n",
    "                tail = ListNode(tmp%10, tail)\n",
    "                one = True\n",
    "            else:\n",
    "                tail = ListNode(tmp, tail)\n",
    "\n",
    "        if one:\n",
    "            tail = ListNode(1, tail)\n",
    "        \n",
    "        return tail\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    flag = 0\n",
    "    def reserve(self, head:ListNode):\n",
    "        pre, cur, nxt = None, head, head\n",
    "        while cur is not None:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reserve(l1)\n",
    "        l2 = self.reserve(l2)\n",
    "        dummy = ListNode(-1)\n",
    "        head = dummy\n",
    "        while l1 is not None and l2 is not None:\n",
    "            Sum = l1.val + l2.val + self.flag\n",
    "            self.flag = 0\n",
    "            if Sum > 9:\n",
    "                self.flag = 1\n",
    "                Sum = Sum % 10\n",
    "            head.next = ListNode(Sum)\n",
    "            head = head.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        if l1 is not None:\n",
    "            while l1 is not None:\n",
    "                Sum = l1.val + self.flag\n",
    "                self.flag = 0\n",
    "                if Sum > 9:\n",
    "                    self.flag = 1\n",
    "                    Sum = Sum % 10\n",
    "                head.next = ListNode(Sum)\n",
    "                head = head.next\n",
    "                l1 = l1.next\n",
    "        elif l2 is not None:\n",
    "            while l2 is not None:\n",
    "                Sum = l2.val + self.flag\n",
    "                self.flag = 0\n",
    "                if Sum > 9:\n",
    "                    self.flag = 1\n",
    "                    Sum = Sum % 10\n",
    "                head.next = ListNode(Sum)\n",
    "                head = head.next\n",
    "                l2 = l2.next\n",
    "\n",
    "        if self.flag == 1:\n",
    "            head.next = ListNode(1)\n",
    "        \n",
    "        return self.reserve(dummy.next) \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        carry, p = 0, None\n",
    "        while s1 or s2 or carry:\n",
    "            num1 = s1.pop() if s1 else 0\n",
    "            num2 = s2.pop() if s2 else 0\n",
    "            ans = num1 + num2 + carry\n",
    "            carry = ans // 10\n",
    "            ans %= 10\n",
    "            p = ListNode(ans, p)\n",
    "        return p\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        s1 = []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        \n",
    "        s2 = []\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        \n",
    "        c = 0\n",
    "        ans = None\n",
    "        while s1 or s2 or c != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            val = a + b + c\n",
    "            c = val // 10\n",
    "            val = val % 10\n",
    "            ans = ListNode(val, ans)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    # 通过栈来解决\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = 0 if not s1 else s1.pop()\n",
    "            b = 0 if not s2 else s2.pop()\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans\n",
    "    \n",
    "    # 递归解决，不过也需要调用栈，而且python递归成本很高\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoAligned(self, l1, l2):\n",
    "        if l1.next is None and l2.next is None:\n",
    "            sum_val = l1.val + l2.val\n",
    "            res = sum_val//10\n",
    "            val = sum_val%10\n",
    "            return res, ListNode(val, None)\n",
    "        \n",
    "        res, return_node = self.addTwoAligned(l1.next, l2.next)\n",
    "        sum_val = l1.val + l2.val + res\n",
    "        res = sum_val//10\n",
    "        val = sum_val%10\n",
    "\n",
    "        return res, ListNode(val, return_node)\n",
    "\n",
    "    def recursive_add(self, node, end_node, res):\n",
    "        \n",
    "        if node == end_node:\n",
    "            sum_val = node.val + res\n",
    "            new_res = sum_val//10\n",
    "            val = sum_val%10\n",
    "            return new_res, ListNode(val, node.next)\n",
    "        \n",
    "        new_res, new_node = self.recursive_add(node.next, end_node, res)\n",
    "        sum_val = node.val + new_res\n",
    "        new_res = sum_val//10\n",
    "        val = sum_val%10\n",
    "\n",
    "        return new_res, ListNode(val, new_node)\n",
    "\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        temp1 = l1\n",
    "        temp2 = l2\n",
    "\n",
    "        length1 = 0\n",
    "        while(temp1 is not None):\n",
    "            temp1 = temp1.next\n",
    "            length1 += 1\n",
    "        length2 = 0\n",
    "        while(temp2 is not None):\n",
    "            temp2 = temp2.next\n",
    "            length2 += 1\n",
    "        \n",
    "        if length1 < length2:\n",
    "            length1, length2 = length2, length1\n",
    "            l1, l2 = l2, l1\n",
    "        \n",
    "        diff_len = length1 - length2\n",
    "\n",
    "        add_head_1 = l1\n",
    "        while(diff_len>0):\n",
    "            add_head_1 = add_head_1.next\n",
    "            diff_len-=1\n",
    "\n",
    "        res, out_head = self.addTwoAligned(add_head_1, l2)\n",
    "\n",
    "        diff_len = length1 - length2\n",
    "\n",
    "        if diff_len == 0:\n",
    "            if res == 0:\n",
    "                return out_head\n",
    "            else:\n",
    "                new_head = ListNode(1, out_head)\n",
    "                return new_head\n",
    "        else:\n",
    "            diff_len = length1 - length2 - 1\n",
    "            add_head_1 = l1\n",
    "            while(diff_len>0):\n",
    "                add_head_1 = add_head_1.next\n",
    "                diff_len-=1\n",
    "            add_head_1.next = out_head\n",
    "\n",
    "            res, out_head = self.recursive_add(l1, add_head_1, res)\n",
    "\n",
    "\n",
    "            if res == 0:\n",
    "                return out_head\n",
    "            else:\n",
    "                new_head = ListNode(1, out_head)\n",
    "                return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        st1, st2 = [], []\n",
    "        dummy = ListNode()\n",
    "        cur = l1\n",
    "        while cur is not None:\n",
    "            st1.append(cur.val)\n",
    "            cur = cur.next\n",
    "        cur = l2\n",
    "        while cur is not None:\n",
    "            st2.append(cur.val)\n",
    "            cur = cur.next\n",
    "        \n",
    "        carry = 0\n",
    "        while len(st1) != 0 and len(st2) != 0:\n",
    "            # 各取一个数字相加\n",
    "            _sum = st1[-1] + st2[-1] + carry\n",
    "            st1.pop()\n",
    "            st2.pop()\n",
    "            carry = _sum // 10\n",
    "            # 头插法\n",
    "            dummy.next = ListNode(val=_sum%10, next=dummy.next)\n",
    "        \n",
    "        # 将较长链表的剩余部分进行头插\n",
    "        for st in [st1, st2]:\n",
    "            while len(st) != 0:\n",
    "                _sum = st[-1] + carry\n",
    "                st.pop()\n",
    "                carry = _sum // 10\n",
    "                dummy.next = ListNode(val=_sum%10, next=dummy.next)\n",
    "        \n",
    "        # 最终进位\n",
    "        if carry == 1:\n",
    "            dummy.next = ListNode(val=1, next=dummy.next)\n",
    "        \n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head: return\n",
    "        cur = head\n",
    "        pre = None\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverse(l1)\n",
    "        l2 = self.reverse(l2)\n",
    "        next1 = 0\n",
    "        pre = None\n",
    "        cur = ListNode(0)\n",
    "\n",
    "        while l1 and l2:\n",
    "            cur_sum = (l1.val + l2.val + next1)\n",
    "            cur = ListNode(cur_sum % 10)\n",
    "            next1 = cur_sum // 10\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        \n",
    "        while l1:\n",
    "            cur_sum = l1.val + next1\n",
    "            next1 = cur_sum // 10\n",
    "            cur = ListNode(cur_sum % 10)\n",
    "            l1 = l1.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        \n",
    "        while l2:\n",
    "            cur_sum = l2.val + next1\n",
    "            next1 = cur_sum // 10\n",
    "            cur = ListNode(cur_sum % 10)\n",
    "            l2 = l2.next\n",
    "            cur.next = pre\n",
    "            pre = cur  \n",
    "\n",
    "        if next1:\n",
    "            cur = ListNode(next1)\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        \n",
    "        return pre\n",
    "\n",
    "\n",
    "\n",
    "    # def reverse(self, head):\n",
    "    #     if not head: return head\n",
    "    #     pre = None\n",
    "    #     cur = head\n",
    "    #     while cur:\n",
    "    #         nxt = cur.next\n",
    "    #         cur.next = pre\n",
    "    #         pre = cur\n",
    "    #         cur = nxt\n",
    "    #     return pre\n",
    "\n",
    "    # def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        \n",
    "\n",
    "        # l1 = self.reverse(l1)\n",
    "        # l2 = self.reverse(l2)\n",
    "        # last = None\n",
    "        \n",
    "        # dummy = ListNode(0)\n",
    "        # cur = dummy\n",
    "        # nxt = 0\n",
    "        # while l1 and l2:\n",
    "        #     cur_sum = l1.val + l2.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l1 = l1.next\n",
    "        #     l2 = l2.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # while l1:\n",
    "        #     cur_sum = l1.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l1 = l1.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # while l2:\n",
    "        #     cur_sum = l2.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l2 = l2.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur  \n",
    "        # if nxt:\n",
    "        #     cur = ListNode(nxt)\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def rev(head):\n",
    "            pre = None\n",
    "            cur = head\n",
    "            while cur:\n",
    "                tmp = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = tmp\n",
    "            return pre\n",
    "        l1 = rev(l1)\n",
    "        l2 = rev(l2)\n",
    "        carry = 0\n",
    "        res = ListNode(0)\n",
    "        cur = res\n",
    "        while l1 or l2 or carry:\n",
    "            tmp = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            res.val = tmp % 10\n",
    "            carry = tmp // 10\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "            if l1 or l2 or carry:\n",
    "                res.next = ListNode(0)\n",
    "                res = res.next\n",
    "        print(cur)\n",
    "        cur = rev(cur)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "# class Solution:\n",
    "    # 翻转链表法\n",
    "    # def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "    #     def reverse(head: ListNode):\n",
    "    #         pre, cur = None, head\n",
    "    #         while cur:\n",
    "    #             nxt = cur.next\n",
    "    #             cur.next = pre\n",
    "    #             pre = cur\n",
    "    #             cur = nxt\n",
    "    #         return pre\n",
    "    #     carry = 0 # 保存进位\n",
    "    #     l1 = reverse(l1)\n",
    "    #     l2 = reverse(l2)\n",
    "    #     dummy = cur = ListNode()\n",
    "    #     while l1 or l2 or carry:\n",
    "    #         sum = carry\n",
    "    #         if l1:\n",
    "    #             sum += l1.val\n",
    "    #             l1 = l1.next\n",
    "    #         if l2:\n",
    "    #             sum += l2.val\n",
    "    #             l2 = l2.next\n",
    "    #         carry = sum // 10\n",
    "    #         sum %= 10\n",
    "    #         cur.next = ListNode(val = sum)\n",
    "    #         cur = cur.next\n",
    "    #     return reverse(dummy.next)\n",
    "\n",
    "class Solution:\n",
    "    # 进阶解法\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        stack1, stack2 = [], [] # 初始化的时候不能设置为 stack1 = stack2 = [], 否则数据错误\n",
    "        while l1:\n",
    "            stack1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            stack2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        dummy = ListNode()\n",
    "        carry = 0\n",
    "        while stack1 or stack2 or carry:\n",
    "            sum = carry\n",
    "            if stack1:\n",
    "                sum += stack1.pop()\n",
    "            if stack2:\n",
    "                sum += stack2.pop()\n",
    "            carry = sum // 10\n",
    "            # 下面这两步巧妙的将链表顺序调整了\n",
    "            node = ListNode(sum % 10, dummy.next)\n",
    "            dummy.next = node\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def reverse(head: ListNode):\n",
    "            pre, cur = None, head\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                cur.next = pre\n",
    "                pre = cur\n",
    "                cur = nxt\n",
    "            return pre\n",
    "        carry = 0 # 保存进位\n",
    "        l1 = reverse(l1)\n",
    "        l2 = reverse(l2)\n",
    "        dummy = cur = ListNode()\n",
    "        while l1 or l2 or carry:\n",
    "            sum = carry\n",
    "            if l1:\n",
    "                sum += l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                sum += l2.val\n",
    "                l2 = l2.next\n",
    "            carry = sum // 10\n",
    "            sum %= 10\n",
    "            cur.next = ListNode(val = sum)\n",
    "            cur = cur.next\n",
    "        return reverse(dummy.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        def list2num(head: ListNode) -> int:\n",
    "            num = 0\n",
    "            node = head\n",
    "            while node != None:\n",
    "                num = num * 10 + node.val\n",
    "                node = node.next\n",
    "            return num\n",
    "        \n",
    "        def num2list(num: int) -> ListNode:\n",
    "            _num = num\n",
    "            last = None\n",
    "            if num != 0:\n",
    "                while _num > 0:\n",
    "                    v = _num % 10\n",
    "                    _num //= 10\n",
    "                    node = ListNode(val=v, next=last)\n",
    "                    last = node\n",
    "            else:\n",
    "                last = ListNode(val=0)\n",
    "            return last\n",
    "        \n",
    "        num = list2num(l1)\n",
    "        num += list2num(l2)\n",
    "        node = num2list(num)\n",
    "\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        p,q = [],[]\n",
    "        while l1:\n",
    "            p.append(l1)\n",
    "            l1=l1.next\n",
    "        while l2:\n",
    "            q.append(l2)\n",
    "            l2=l2.next\n",
    "        c=0\n",
    "        newHead=None\n",
    "        while len(p) and len(q):\n",
    "            a,b=p.pop(),q.pop()\n",
    "            t=(a.val+b.val+c)%10\n",
    "            c=(a.val+b.val+c)//10\n",
    "            newNode = ListNode(t,newHead)\n",
    "            newHead = newNode\n",
    "        while len(p):\n",
    "            a=p.pop()\n",
    "            t=(a.val+c)%10\n",
    "            c=(a.val+c)//10\n",
    "            newNode = ListNode(t,newHead)\n",
    "            newHead = newNode\n",
    "        while len(q):\n",
    "            b=q.pop()\n",
    "            t=(b.val+c)%10\n",
    "            c=(b.val+c)//10\n",
    "            newNode = ListNode(t,newHead)\n",
    "            newHead = newNode\n",
    "        if c:\n",
    "            newNode = ListNode(c,newHead)\n",
    "            newHead = newNode\n",
    "        return newHead\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            list1, list2 = [], []\n",
    "            while l1:\n",
    "                list1.append(l1.val)\n",
    "                l1 = l1.next\n",
    "            while l2:\n",
    "                list2.append(l2.val)\n",
    "                l2 = l2.next\n",
    "            list1 = list1[::-1]\n",
    "            list2 = list2[::-1]\n",
    "            n = max(len(list1), len(list2))\n",
    "            arr = [0] * (n + 1)\n",
    "            for i in range(n):\n",
    "                if i < len(list1):\n",
    "                    arr[i] += list1[i]\n",
    "                if i < len(list2):\n",
    "                    arr[i] += list2[i]\n",
    "                \n",
    "                if arr[i] >= 10:\n",
    "                    arr[i + 1] += 1\n",
    "                    arr[i] -= 10\n",
    "            if arr[-1] == 0: arr.pop()\n",
    "            res = None\n",
    "            for num in arr:\n",
    "                res = ListNode(num, next = res)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "\n",
    "    def reverse(self, head):\n",
    "        if not head: return\n",
    "        cur = head\n",
    "        pre = None\n",
    "        while cur:\n",
    "            nxt = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = nxt\n",
    "        return pre\n",
    "\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1 = self.reverse(l1)\n",
    "        l2 = self.reverse(l2)\n",
    "        pre = None\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        nxt = 0\n",
    "        while l1 and l2:\n",
    "            cur_sum = (l1.val + l2.val + nxt)\n",
    "            cur= ListNode(cur_sum % 10)\n",
    "            nxt = cur_sum // 10\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        while l1:\n",
    "            cur_sum = (l1.val + nxt)\n",
    "            cur = ListNode(cur_sum % 10)\n",
    "            nxt = cur_sum // 10\n",
    "            l1 = l1.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        \n",
    "        while l2:\n",
    "            cur_sum = l2.val + nxt\n",
    "            nxt = cur_sum // 10\n",
    "            cur = ListNode(cur_sum % 10)\n",
    "            l2 = l2.next\n",
    "            cur.next = pre\n",
    "            pre = cur  \n",
    "        \n",
    "        if nxt:\n",
    "            cur = ListNode(nxt)\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "        \n",
    "        return cur\n",
    "\n",
    "    # def reverse(self, head):\n",
    "    #     if not head: return head\n",
    "    #     pre = None\n",
    "    #     cur = head\n",
    "    #     while cur:\n",
    "    #         nxt = cur.next\n",
    "    #         cur.next = pre\n",
    "    #         pre = cur\n",
    "    #         cur = nxt\n",
    "    #     return pre\n",
    "\n",
    "    # def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        \n",
    "\n",
    "        # l1 = self.reverse(l1)\n",
    "        # l2 = self.reverse(l2)\n",
    "        # last = None\n",
    "        \n",
    "        # dummy = ListNode(0)\n",
    "        # cur = dummy\n",
    "        # nxt = 0\n",
    "        # while l1 and l2:\n",
    "        #     cur_sum = l1.val + l2.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l1 = l1.next\n",
    "        #     l2 = l2.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # while l1:\n",
    "        #     cur_sum = l1.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l1 = l1.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # while l2:\n",
    "        #     cur_sum = l2.val + nxt\n",
    "        #     nxt = cur_sum // 10\n",
    "        #     cur = ListNode(cur_sum % 10)\n",
    "        #     l2 = l2.next\n",
    "        #     cur.next = last\n",
    "        #     last = cur  \n",
    "        # if nxt:\n",
    "        #     cur = ListNode(nxt)\n",
    "        #     cur.next = last\n",
    "        #     last = cur\n",
    "        \n",
    "        # return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1, s2 = [], []\n",
    "        while l1:\n",
    "            s1.append(l1.val)\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s2.append(l2.val)\n",
    "            l2 = l2.next\n",
    "        ans = None\n",
    "        carry = 0\n",
    "        while s1 or s2 or carry != 0:\n",
    "            a = s1.pop() if s1 else 0\n",
    "            b = s2.pop() if s2 else 0\n",
    "            cur = a + b + carry\n",
    "            carry = cur // 10\n",
    "            cur %= 10\n",
    "            curnode = ListNode(cur)\n",
    "            curnode.next = ans\n",
    "            ans = curnode\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        sum_dummy = ListNode(-1)\n",
    "        p = sum_dummy\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:\n",
    "            val1 = l1.val if l1 else 0\n",
    "            l1 = l1.next if l1 else l1\n",
    "            val2 = l2.val if l2 else 0\n",
    "            l2 = l2.next if l2 else l2\n",
    "            p.next = ListNode((val1 + val2 + carry) % 10)\n",
    "            p = p.next\n",
    "            carry = (val1 + val2 + carry) // 10\n",
    "        return sum_dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        res = ListNode()\n",
    "        node_res = res\n",
    "        flag = 0\n",
    "        while l1 != None or l2 != None or flag != 0:\n",
    "            v1, v2 = 0, 0\n",
    "            if l1 != None:\n",
    "                v1 = l1.val\n",
    "                l1 = l1.next\n",
    "            if l2 != None:\n",
    "                v2 = l2.val\n",
    "                l2 = l2.next\n",
    "            sum_ = v1 + v2 + flag\n",
    "            flag = sum_ // 10\n",
    "            v = sum_ % 10\n",
    "            new_node = ListNode(v)\n",
    "            node_res.next = new_node\n",
    "            node_res = node_res.next\n",
    "\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        left, right = l1, l2\n",
    "        left_list, right_list = [], []\n",
    "        new = ListNode(0)\n",
    "        i = 0\n",
    "        while left:\n",
    "            left_list.append(left.val * 10 ** i)\n",
    "            left = left.next\n",
    "            i += 1\n",
    "        i = 0\n",
    "        while right:\n",
    "            right_list.append(right.val * 10 ** i)\n",
    "            right = right.next\n",
    "            i += 1\n",
    "        add = str(sum(left_list) + sum(right_list))\n",
    "        add = add[::-1]\n",
    "        s = list(map(int, add))\n",
    "        head = new\n",
    "        i = 0\n",
    "        while head:\n",
    "            if i == len(s):\n",
    "                head.next = None\n",
    "                break\n",
    "            head.next = ListNode(s[i])\n",
    "            head = head.next\n",
    "            i += 1\n",
    "        return new.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        cur = ans = ListNode()\n",
    "        carry = 0\n",
    "        while carry or l1 or l2:\n",
    "            val = carry  + (l1.val if l1 else 0)+(l2.val if l2 else 0)\n",
    "            carry,val = divmod(val,10)\n",
    "            cur.next = ListNode(val)\n",
    "            cur= cur.next\n",
    "            l1 = l1.next if  l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        res = cur = ListNode()\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:\n",
    "            cur.next = ListNode(((l1.val if l1 else 0) + (l2.val if l2 else 0) + carry) % 10)\n",
    "            carry = ((l1.val if l1 else 0) + (l2.val if l2 else 0) + carry) // 10\n",
    "            l1 = l1.next if l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "            cur = cur.next\n",
    "        return res.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        add_next = 0\n",
    "\n",
    "        null_head = ListNode(0)\n",
    "        cur = null_head\n",
    "        while l1 and l2:\n",
    "            val = (l1.val + l2.val + add_next)%10\n",
    "            add_next = (l1.val + l2.val + add_next)//10\n",
    "            l1, l2 = l1.next, l2.next\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next \n",
    "        while l1:\n",
    "            val = (l1.val + add_next)%10\n",
    "            add_next = (l1.val + add_next)//10\n",
    "            l1 = l1.next\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "\n",
    "        while l2:\n",
    "            val = (l2.val + add_next)%10\n",
    "            add_next = (l2.val + add_next)//10\n",
    "            l2 = l2.next\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "        if add_next != 0:\n",
    "            cur.next = ListNode(add_next)\n",
    "        return null_head.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1 and not l2:   return 0\n",
    "        count1 = 0\n",
    "        res = 0\n",
    "        while l1 != None:\n",
    "            res += l1.val * 10 ** count1\n",
    "            count1 += 1\n",
    "            l1 = l1.next\n",
    "\n",
    "        count2 = 0\n",
    "        while l2 != None:\n",
    "            res += l2.val * 10 ** count2\n",
    "            count2 += 1\n",
    "            l2 = l2.next\n",
    "        res = list(str(res))\n",
    "        head = p = ListNode(int(res.pop()))\n",
    "        while res:\n",
    "            p.next = ListNode(int(res.pop()))\n",
    "            p = p.next\n",
    "        return head\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head = ListNode(-1)\n",
    "        p = head\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:            \n",
    "            n = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry = n // 10  # 取十位上的数\n",
    "            p.next = ListNode(n % 10)\n",
    "            p = p.next\n",
    "            l1, l2 = l1.next if l1 else None, l2.next if l2 else None\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        bring = 0\n",
    "        dummynode = ListNode(0)\n",
    "        node = dummynode\n",
    "        while l1 and l2:\n",
    "            tmp = l1.val + l2.val + bring\n",
    "            node.next = ListNode(tmp%10)\n",
    "            bring = tmp//10\n",
    "            node = node.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        while l1:\n",
    "            tmp = l1.val + bring\n",
    "            node.next = ListNode(tmp%10)\n",
    "            bring = tmp//10\n",
    "            node = node.next\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            tmp = l2.val + bring\n",
    "            node.next = ListNode(tmp%10)\n",
    "            bring = tmp//10\n",
    "            node = node.next\n",
    "            l2 = l2.next\n",
    "        if bring:\n",
    "            node.next = ListNode(bring)\n",
    "        return dummynode.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        num1=k=0\n",
    "        while l1:\n",
    "            num1+=l1.val*10**k\n",
    "            k+=1\n",
    "            l1=l1.next\n",
    "        num2=k=0\n",
    "        while l2:\n",
    "            num2+=l2.val*10**k\n",
    "            k+=1\n",
    "            l2=l2.next\n",
    "        num=num1+num2\n",
    "        dummyhead=ListNode()\n",
    "        pre=dummyhead\n",
    "        while num:\n",
    "            a=num%10\n",
    "            num//=10\n",
    "            node=ListNode(a)\n",
    "            pre.next=node\n",
    "            pre=node\n",
    "        if not dummyhead.next:\n",
    "            dummyhead.next=ListNode(0)\n",
    "        return dummyhead.next \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l1 is None:\n",
    "            return l2\n",
    "        if l2 is None:\n",
    "            return l1\n",
    "        head = l1\n",
    "        flag = 0\n",
    "        while l2 is not None or flag == 1:\n",
    "            val = 0\n",
    "            if l2 is not None:\n",
    "                val = l2.val\n",
    "                l2 = l2.next\n",
    "            l1.val, flag = (l1.val + val + flag) % 10, (l1.val + val + flag) // 10\n",
    "            if (l2 is not None or flag == 1) and l1.next is None:\n",
    "                l1.next = ListNode(0)\n",
    "            l1 = l1.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        c = 0\n",
    "        pre = dummy = ListNode(0)\n",
    "        while l1 or l2:\n",
    "            v1 = l1.val if l1 else 0\n",
    "            v2 = l2.val if l2 else 0\n",
    "            pre.next = ListNode((v1 + v2 + c) % 10)\n",
    "            pre = pre.next\n",
    "            c = (v1 + v2 + c) // 10\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "        if c != 0:\n",
    "            pre.next = ListNode(c)\n",
    "        return dummy.next\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        \n",
    "        dummyNode = ListNode(0)\n",
    "        head = dummyNode\n",
    "        carry = 0\n",
    "        while l1 or l2:\n",
    "            n1, n2 = 0, 0\n",
    "\n",
    "            if l1:\n",
    "                n1 = l1.val\n",
    "                l1 = l1.next\n",
    "\n",
    "            if l2:\n",
    "                n2 = l2.val\n",
    "                l2 = l2.next\n",
    "\n",
    "\n",
    "            carry, mod = divmod(n1+n2+carry, 10)\n",
    "            head.next = ListNode(mod)\n",
    "            head = head.next\n",
    "\n",
    "        if carry > 0:\n",
    "            head.next = ListNode(carry)\n",
    "\n",
    "        return dummyNode.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "\n",
    "        node = ListNode()\n",
    "        p = node\n",
    "        next_int = 0\n",
    "        while l1 or l2 or next_int:\n",
    "\n",
    "            n = (l1.val if l1 else 0) + (l2.val if l2 else 0) + next_int\n",
    "            next_int = n // 10\n",
    "            p.next = ListNode(n % 10)\n",
    "            p = p.next\n",
    "\n",
    "            l1 = l1.next if l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "\n",
    "        return node.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        dummy_node=ListNode(-1)\n",
    "        node=dummy_node\n",
    "        val=0\n",
    "        while l1 or l2:\n",
    "            if l1:\n",
    "                val+=l1.val\n",
    "                l1=l1.next\n",
    "            if l2:\n",
    "                val+=l2.val\n",
    "                l2=l2.next\n",
    "            node.next=ListNode((val)%10)\n",
    "            node=node.next\n",
    "            val//=10\n",
    "        if val:\n",
    "            node.next=ListNode(val)\n",
    "        return dummy_node.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        r=head=ListNode()\n",
    "        flag=0\n",
    "        while l1 or l2:\n",
    "            num1=l1.val if l1 else 0\n",
    "            num2=l2.val if l2 else 0\n",
    "            num = num1 + num2 + flag\n",
    "            r.next=ListNode(num%10)\n",
    "            r=r.next\n",
    "            flag = 1 if num>9 else 0\n",
    "            if l1:\n",
    "                l1=l1.next\n",
    "            if l2:\n",
    "                l2=l2.next\n",
    "        if flag==1:\n",
    "            r.next=ListNode(1)\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        carry = 0\n",
    "        cur = ans = ListNode()\n",
    "        while carry or l1 or l2:\n",
    "            val = carry +(l1.val if l1 else 0)+(l2.val if l2 else 0)\n",
    "            carry,val = divmod(val,10)\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "            l1 = l1.next if l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head = ListNode(-1)\n",
    "        p = head\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:            \n",
    "            n = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry = n // 10  # 取十位上的数\n",
    "            p.next = ListNode(n % 10)\n",
    "            p = p.next\n",
    "            l1, l2 = l1.next if l1 else None, l2.next if l2 else None\n",
    "        return head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        d = ListNode()\n",
    "        r = d\n",
    "        p, q = l1, l2\n",
    "        c = 0\n",
    "        while p is not None or q is not None or c > 0:\n",
    "            v1 = 0 if p is None else p.val\n",
    "            v2 = 0 if q is None else q.val\n",
    "            r.next = ListNode((v1+v2+c)%10)\n",
    "            c = (v1+v2+c)//10\n",
    "            r = r.next\n",
    "            p = None if p is None else p.next\n",
    "            q = None if q is None else q.next\n",
    "        return d.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "                return self.add(l1,l2,0)\n",
    "    def add(self,l1,l2,mark):\n",
    "        if not l2 and not l1:\n",
    "            if mark:\n",
    "                return ListNode(1)\n",
    "            return None\n",
    "        if not l2:\n",
    "            val=l1.val+mark\n",
    "            l1=l1.next\n",
    "        elif not l1:\n",
    "            val=l2.val+mark\n",
    "            l2=l2.next\n",
    "        else:\n",
    "            val=l2.val+l1.val+mark\n",
    "            l2,l1=l2.next,l1.next\n",
    "        if val>9:\n",
    "            Node=ListNode(val-10)\n",
    "            mark=1\n",
    "        else:\n",
    "            Node=ListNode(val)\n",
    "            mark=0\n",
    "        Node.next=self.add(l1,l2,mark)\n",
    "        return Node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        add=0\n",
    "        h=p=ListNode(0)\n",
    "        while l1 or l2 or add!=0:\n",
    "            x1,x2=0,0\n",
    "            if l1:\n",
    "                x1=l1.val\n",
    "            if l2:\n",
    "                x2=l2.val\n",
    "            result=x1+x2+add\n",
    "            add=result//10\n",
    "            p.next=ListNode(result%10)\n",
    "            p=p.next\n",
    "            if l1:\n",
    "                l1=l1.next\n",
    "            if l2:\n",
    "                l2=l2.next\n",
    "        return h.next\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        node=ListNode(0)\n",
    "        head=node\n",
    "        val=0\n",
    "        while l1 or l2:\n",
    "            if l1:\n",
    "                val+=l1.val\n",
    "                l1=l1.next\n",
    "            if l2:\n",
    "                val+=l2.val\n",
    "                l2=l2.next\n",
    "            node.next=ListNode((val)%10)\n",
    "            val//=10\n",
    "            node=node.next\n",
    "        if val:\n",
    "            node.next=ListNode(val)\n",
    "        return head.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1:\n",
    "            return l2\n",
    "\n",
    "        if not l2:\n",
    "            return l1\n",
    "        \n",
    "        dummy = ListNode()\n",
    "        head = dummy\n",
    "        carry = 0\n",
    "\n",
    "        while l1 or l2 or carry:\n",
    "            if l1:\n",
    "                carry += l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                carry += l2.val\n",
    "                l2 = l2.next\n",
    "            \n",
    "            carry, val = divmod(carry, 10)\n",
    "            head.next = ListNode(val)\n",
    "            head = head.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "#         last_remain = 0     \n",
    "        \n",
    "#         dummy = ListNode()\n",
    "#         dummy.next = l1\n",
    "#         pre = dummy\n",
    "#         while l1:\n",
    "#             if l2:\n",
    "#                 tmp = l1.val + l2.val + last_remain\n",
    "#             else:\n",
    "#                 tmp = l1.val + last_remain\n",
    "#             print(tmp)\n",
    "#             node = ListNode()\n",
    "#             node.val = tmp % 10\n",
    "#             last_remain = tmp // 10\n",
    "#             pre.next = node\n",
    "#             pre = pre.next\n",
    "#             l1 = l1.next\n",
    "#             l2 = l2.next\n",
    "\n",
    "#         if l2:\n",
    "#             pre.next = l2\n",
    "        \n",
    "#         return dummy\n",
    " \n",
    "\n",
    "        head = ListNode(-1)\n",
    "        p = head\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:            \n",
    "            n = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry = n // 10  # 取十位上的数\n",
    "            p.next = ListNode(n % 10)\n",
    "            p = p.next\n",
    "            l1, l2 = l1.next if l1 else None, l2.next if l2 else None\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        carry = 0\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        while l1 or l2:\n",
    "            a = l1.val if l1 else 0\n",
    "            b = l2.val if l2 else 0\n",
    "            tmp = a + b + carry\n",
    "            carry = tmp // 10\n",
    "            tmp %= 10\n",
    "            cur.next = ListNode(tmp)\n",
    "            cur = cur.next\n",
    "            l1 = l1.next if l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "        if carry != 0:\n",
    "            cur.next = ListNode(carry)\n",
    "\n",
    "        \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head = ListNode(-1)\n",
    "        p = head\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:            \n",
    "            n = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry = n // 10  # 取十位上的数\n",
    "            p.next = ListNode(n % 10)\n",
    "            p = p.next\n",
    "            l1, l2 = l1.next if l1 else None, l2.next if l2 else None\n",
    "        return head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        # print(l1,l2)\n",
    "        dummy0 = ListNode(-1)\n",
    "        dummy = dummy0\n",
    "        b = 0\n",
    "        while l1 or l2:\n",
    "            l1_val = l1.val if l1 else 0\n",
    "            l2_val = l2.val if l2 else 0\n",
    "            a = l1_val+l2_val\n",
    "            # a = l1.val if l1 else 0 +l2.val if l2 else 0\n",
    "            # print(a,b)         \n",
    "            cur = ListNode((a+b)%10)\n",
    "            dummy.next = cur\n",
    "            b = 1 if a+b >= 10 else 0\n",
    "            dummy = dummy.next\n",
    "            # if l1 != None: l1 = l1.next\n",
    "            # if l2 != None: l2 = l2.next\n",
    "            l1 = l1.next if l1 else 0\n",
    "            l2 = l2.next if l2 else 0\n",
    "            if b>0: dummy.next = ListNode(1)\n",
    "        return dummy0.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        x=0\n",
    "        s=l1\n",
    "        p=0\n",
    "        while s:\n",
    "            x+=s.val*10**p\n",
    "            p+=1\n",
    "            s=s.next\n",
    "        s=l2\n",
    "        p=0\n",
    "        while s:\n",
    "            x+=s.val*10**p\n",
    "            p+=1\n",
    "            s=s.next\n",
    "        ans=ListNode(0)\n",
    "        y=ans\n",
    "        while x>0:\n",
    "            y.next=(ListNode(x%10))\n",
    "            x//=10\n",
    "            y=y.next\n",
    "        return ans.next if ans.next else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "# 使用数组存储然后相加的形式都会导致大数溢出\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        carry = 0\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "\n",
    "        while l1 or l2:\n",
    "            x = l1.val if l1 else 0\n",
    "            y = l2.val if l2 else 0\n",
    "            _sum = (x + y + carry) % 10\n",
    "            carry = (x + y + carry) // 10\n",
    "            cur.next = ListNode(_sum)\n",
    "            cur = cur.next\n",
    "\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "        if carry > 0:\n",
    "            cur.next = ListNode(carry)\n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        ans = ListNode(0)\n",
    "        pre = ans\n",
    "        jw = 0\n",
    "        while l1 or l2 or jw:\n",
    "            num = jw\n",
    "            jw = 0\n",
    "            if l1:\n",
    "                num += l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                num += l2.val\n",
    "                l2 = l2.next\n",
    "            if num >= 10:\n",
    "                num -= 10\n",
    "                jw = 1\n",
    "            node = ListNode(num)\n",
    "            pre.next = node\n",
    "            pre = node\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l1 is None and l2 is None:\n",
    "            return None\n",
    "        elif l1 is not None and l2 is None:\n",
    "            return l1\n",
    "        elif l1 is None and l2 is not None:\n",
    "            return l2\n",
    "        \n",
    "        curr_l1 = l1\n",
    "        curr_l2 = l2\n",
    "        ans_dummy = ListNode(0)\n",
    "        curr_ans = ans_dummy\n",
    "        # 是否需要进位\n",
    "        lt10 = False\n",
    "\n",
    "        while True:\n",
    "            if curr_l1 is None and curr_l2 is None and lt10 == False:\n",
    "                break\n",
    "\n",
    "            curr_sum = 0\n",
    "            if curr_l1 is not None:\n",
    "                curr_sum += curr_l1.val\n",
    "            if curr_l2 is not None:\n",
    "                curr_sum += curr_l2.val\n",
    "            if lt10:\n",
    "                curr_sum += 1\n",
    "                lt10 = False\n",
    "            \n",
    "            if curr_sum >= 10:\n",
    "                curr_sum = curr_sum - 10\n",
    "                lt10 = True\n",
    "            \n",
    "            curr_node = ListNode(curr_sum)\n",
    "            curr_ans.next = curr_node\n",
    "            curr_ans = curr_ans.next\n",
    "            if curr_l1 is not None:\n",
    "                curr_l1 = curr_l1.next\n",
    "            if curr_l2 is not None:\n",
    "                curr_l2 = curr_l2.next\n",
    "\n",
    "        return ans_dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        temp = 0\n",
    "        l3 = ListNode(-1,None)\n",
    "        head1 = l1\n",
    "        head2 = l2 \n",
    "        head3 = l3\n",
    "        while head1 != None and head2 != None:\n",
    "            t = head1.val + head2.val + temp\n",
    "            if t >= 10:\n",
    "                t = t%10\n",
    "                temp = 1\n",
    "                head3.next = ListNode(t,None)\n",
    "            else:\n",
    "                temp = 0\n",
    "                head3.next = ListNode(t,None)\n",
    "            head1 = head1.next\n",
    "            head2 = head2.next\n",
    "            head3 = head3.next\n",
    "\n",
    "        while head1 != None:\n",
    "            t = head1.val + temp\n",
    "            if t >= 10:\n",
    "                t = t%10\n",
    "                \n",
    "                temp = 1\n",
    "                head3.next = ListNode(t,None)\n",
    "            else:\n",
    "                temp = 0\n",
    "                head3.next = ListNode(t,None)\n",
    "            head1 = head1.next\n",
    "            head3 = head3.next\n",
    "        \n",
    "        while head2 != None:\n",
    "            t = head2.val + temp\n",
    "            if t >= 10:\n",
    "                t = t%10\n",
    "                temp = 1\n",
    "                head3.next = ListNode(t,None)\n",
    "            else:\n",
    "                temp = 0\n",
    "                head3.next = ListNode(t,None)\n",
    "            head2 = head2.next\n",
    "            head3 = head3.next\n",
    "        if temp == 1:\n",
    "            head3.next = ListNode(1,None)\n",
    "        return l3.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur=dummy=ListNode()\n",
    "        carry=0\n",
    "        while l1 or l2 or carry:\n",
    "            carry += (l1.val if l1 else 0)+(l2.val if l2 else 0)\n",
    "            cur.next=ListNode(carry%10)\n",
    "            carry//=10\n",
    "            cur=cur.next\n",
    "            if l1: \n",
    "                l1 = l1.next  # 下一个节点\n",
    "            if l2: \n",
    "                l2 = l2.next  # 下一个节点\n",
    "        return dummy.next  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        sumret=carry=0\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        while l1 and l2:\n",
    "            sumret = l1.val+l2.val+carry\n",
    "            carry = sumret//10\n",
    "            cur.next = ListNode(sumret%10)\n",
    "            cur=cur.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        while l1:\n",
    "            sumret = l1.val+carry\n",
    "            carry = sumret//10\n",
    "            cur.next = ListNode(sumret%10)\n",
    "            cur=cur.next\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            sumret = l2.val+carry\n",
    "            carry = sumret//10\n",
    "            cur.next = ListNode(sumret%10)\n",
    "            cur=cur.next\n",
    "            l2 = l2.next\n",
    "        if carry > 0:\n",
    "            cur.next = ListNode(carry)\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        cur1 =l1\n",
    "        cur2 = l2\n",
    "        head = ListNode(None)\n",
    "        cur = head\n",
    "        add = 0\n",
    "        while cur1 and cur2:\n",
    "            if cur1.val + cur2.val + add < 10:\n",
    "                cur.next = ListNode(cur1.val + cur2.val+add)\n",
    "                add = 0\n",
    "            else:\n",
    "                cur.next = ListNode(cur1.val + cur2.val+add-10)\n",
    "                add = 1\n",
    "            cur = cur.next\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next\n",
    "        if add == 1:\n",
    "            if not cur1 and not cur2:\n",
    "                cur.next = ListNode(1)\n",
    "            if cur1:\n",
    "                flag = 1\n",
    "                while flag == 1:\n",
    "                    if cur1.val + 1 < 10:\n",
    "                        flag = 0\n",
    "                        cur.next = ListNode(cur1.val+1)\n",
    "                        if cur1.next:\n",
    "                            cur.next.next = cur1.next\n",
    "                    else:\n",
    "                        cur.next = ListNode(cur1.val+1-10)\n",
    "                        if not cur1.next:\n",
    "                            flag = 0\n",
    "                            cur.next.next = ListNode(1)\n",
    "                        else:\n",
    "                            cur1 = cur1.next\n",
    "                            flag = 1\n",
    "                            cur = cur.next\n",
    "                    \n",
    "            if cur2:\n",
    "                flag2 = 1\n",
    "                while flag2 == 1:\n",
    "                    if cur2.val + 1 < 10:\n",
    "                        flag2 = 0\n",
    "                        cur.next = ListNode(cur2.val+1)\n",
    "                        if cur2.next:\n",
    "                            cur.next.next = cur2.next\n",
    "                    else:\n",
    "                        cur.next = ListNode(cur2.val+1-10)\n",
    "                        if not cur2.next:\n",
    "                            flag2 = 0\n",
    "                            cur.next.next = ListNode(1)\n",
    "                        else:\n",
    "                            cur2 = cur2.next\n",
    "                            flag2 = 1\n",
    "                            cur = cur.next\n",
    "            return head.next            \n",
    "        else:\n",
    "            if cur1:\n",
    "                cur.next = cur1\n",
    "            if cur2:\n",
    "                cur.next = cur2\n",
    "            return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        s1 = ''\n",
    "        s2 = ''\n",
    "        curr = l1\n",
    "        def rev(s):\n",
    "            ans = ''\n",
    "            for i in reversed(s):\n",
    "                ans += i\n",
    "            return int(ans)\n",
    "        while curr:\n",
    "            s1 += str(curr.val)\n",
    "            curr = curr.next\n",
    "        curr = l2\n",
    "        while curr:\n",
    "            s2 += str(curr.val)\n",
    "            curr = curr.next\n",
    "        s = str(rev(s1) + rev(s2))\n",
    "        i = 0\n",
    "        dummy = ListNode()\n",
    "        curr = dummy\n",
    "        while i < len(s):\n",
    "            curr.next = ListNode(int(s[len(s) - 1 - i]))\n",
    "            curr = curr.next\n",
    "            i += 1\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "\n",
    "        res = ListNode(0)\n",
    "        rec = res\n",
    "        digit, acc = 0, 0\n",
    "\n",
    "        while l1 and l2:\n",
    "            s = l1.val + l2.val + acc\n",
    "            digit = s % 10\n",
    "            acc = s // 10\n",
    "            res.next = ListNode(digit)\n",
    "            res = res.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        while l1:\n",
    "            s = l1.val + acc\n",
    "            digit = s % 10\n",
    "            acc = s // 10\n",
    "            res.next = ListNode(digit)\n",
    "            res = res.next\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s = l2.val + acc\n",
    "            digit = s % 10\n",
    "            acc = s // 10\n",
    "            res.next = ListNode(digit)\n",
    "            res = res.next\n",
    "            l2 = l2.next\n",
    "        if acc:\n",
    "            res.next = ListNode(1)\n",
    "            res = res.next\n",
    "        return rec.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        ans = ListNode(-1)\n",
    "        p = ans\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:\n",
    "            n = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry = n // 10\n",
    "            p.next = ListNode(n % 10)\n",
    "            p = p.next\n",
    "            l1, l2 = l1.next if l1 else None, l2.next if l2 else None\n",
    "\n",
    "        return ans.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        dummy=ListNode(-1)\n",
    "        p=dummy\n",
    "        tmp=0\n",
    "        while l1 or l2 or tmp:\n",
    "            n=(l1.val if l1 else 0)+(l2.val if l2 else 0)+tmp\n",
    "            tmp=n//10\n",
    "            p.next=ListNode(n%10)\n",
    "            p=p.next\n",
    "            l1=l1.next if l1 else None\n",
    "            l2=l2.next if l2 else None\n",
    "        return dummy.next\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        plus = 0\n",
    "        ret = ListNode(0)\n",
    "        head = ret\n",
    "        while l1 and l2:\n",
    "            tmp = l1.val + l2.val + plus\n",
    "            plus = tmp // 10\n",
    "            ret.next = ListNode(tmp % 10)\n",
    "            ret = ret.next\n",
    "            l1, l2 = l1.next, l2.next\n",
    "        l1 = l1 if l1 else l2\n",
    "        while l1:\n",
    "            tmp = l1.val + plus\n",
    "            plus = tmp // 10\n",
    "            ret.next = ListNode(tmp % 10)\n",
    "            ret = ret.next\n",
    "            l1 = l1.next\n",
    "        if plus:\n",
    "            ret.next = ListNode(plus)\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        ans = ListNode(0)\n",
    "        out = ans\n",
    "        add_flag = 0\n",
    "        while l1 or l2:\n",
    "            if l1 and l2:\n",
    "                sum_ = l1.val + l2.val + add_flag\n",
    "                l1 = l1.next\n",
    "                l2 = l2.next\n",
    "            elif l1 and not l2:\n",
    "                sum_ = l1.val + add_flag\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                sum_ = l2.val + add_flag\n",
    "                l2 = l2.next\n",
    "            add_flag = 1 if sum_ >= 10 else 0\n",
    "            sum_ = sum_ % 10\n",
    "            ans.next = ListNode(sum_)\n",
    "            ans = ans.next\n",
    "        if add_flag != 0:\n",
    "            ans.next = ListNode(add_flag)\n",
    "            ans = ans.next\n",
    "        return out.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        #栈 \n",
    "        head=None \n",
    "        carry=0 \n",
    "        while l1!=None or l2!=None:\n",
    "            if l1 is not None:\n",
    "                n1=l1.val \n",
    "            else:\n",
    "                n1=0 \n",
    "            if l2 is not None:\n",
    "                n2=l2.val \n",
    "            else:\n",
    "                n2=0 \n",
    "            sums=n1+n2+carry \n",
    "            if head is None:\n",
    "                head=ListNode(sums%10)\n",
    "                tail=head \n",
    "            else:\n",
    "                tail.next=ListNode(sums%10)\n",
    "                tail=tail.next \n",
    "            carry=sums//10 \n",
    "            if l1!=None:\n",
    "                l1=l1.next \n",
    "            if l2!=None:\n",
    "                l2=l2.next \n",
    "        if carry>0:\n",
    "            tail.next=ListNode(carry)\n",
    "        return head \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head = ListNode(-1)\n",
    "        p = head\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:            \n",
    "            n = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry = n // 10  # 取十位上的数\n",
    "            p.next = ListNode(n % 10)\n",
    "            p = p.next\n",
    "            l1, l2 = l1.next if l1 else None, l2.next if l2 else None\n",
    "        return head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        res = ListNode(0)\n",
    "        cur = res\n",
    "        rem = 0\n",
    "        while l1 or l2:\n",
    "            val1 = l1.val if l1 else 0\n",
    "            val2 = l2.val if l2 else 0\n",
    "            sum = (val1 + val2 + rem)\n",
    "            val = sum % 10\n",
    "            rem = sum // 10\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "        if rem > 0:\n",
    "            cur.next = ListNode(rem)\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        cur=dummy=ListNode()\n",
    "        carry=0\n",
    "        while l1 or l2 or carry:\n",
    "            carry += (l1.val if l1 else 0)+(l2.val if l2 else 0)\n",
    "            cur.next=ListNode(carry%10)\n",
    "            carry//=10\n",
    "            cur=cur.next\n",
    "            if l1: \n",
    "                l1 = l1.next  # 下一个节点\n",
    "            if l2: \n",
    "                l2 = l2.next  # 下一个节点\n",
    "        return dummy.next  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        carry = 0\n",
    "        cur = ans = ListNode()\n",
    "        while carry or l1 or l2:\n",
    "            val = carry + (l1.val if l1 else 0)+(l2.val if l2 else 0)\n",
    "            carry,val = divmod(val,10)\n",
    "            cur.next = ListNode(val)\n",
    "            cur = cur.next\n",
    "            l1 = l1.next if l1 else None\n",
    "            l2 = l2.next if l2 else None\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        c, pre = 0, None\n",
    "        ans = l1\n",
    "        while l1 and l2:\n",
    "            l1.val += l2.val + c\n",
    "            c = 1 if l1.val >= 10 else 0\n",
    "            l1.val = l1.val-10 if l1.val >= 10 else l1.val\n",
    "            pre = l1\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "\n",
    "        if l1 == None:\n",
    "            pre.next = l2\n",
    "            l1 = l2\n",
    "        while l1:\n",
    "            l1.val += c\n",
    "            c = 1 if l1.val >= 10 else 0\n",
    "            l1.val = l1.val-10 if l1.val >= 10 else l1.val\n",
    "            pre = l1\n",
    "            l1 = l1.next\n",
    "        if c:\n",
    "            pre.next = ListNode(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        p1=l1\n",
    "        p2=l2\n",
    "        jw=0\n",
    "        p0=p1\n",
    "        while p1 is not None and p2 is not None:\n",
    "            he=p1.val+p2.val+jw\n",
    "            jw=he//10\n",
    "            p1.val=he%10\n",
    "            p0=p1\n",
    "            p1=p1.next\n",
    "\n",
    "            p2=p2.next\n",
    "\n",
    "        \n",
    "        while p1 is not None:\n",
    "            he=p1.val+jw\n",
    "            p1.val=he%10\n",
    "            jw=he//10\n",
    "            print('ttt',p1.val)\n",
    "            p0=p1\n",
    "            p1=p1.next\n",
    "            if jw==0:\n",
    "                break\n",
    "\n",
    "        p1=p0\n",
    "        print(p1,p2)\n",
    "        if p2 is not None:\n",
    "            p1.next=p2\n",
    "            while p2 is not None:\n",
    "                \n",
    "                he=p2.val+jw\n",
    "                p2.val=he%10\n",
    "                jw=he//10\n",
    "                \n",
    "                p1=p2\n",
    "                p2=p2.next\n",
    "                if jw==0:\n",
    "                    break\n",
    "                \n",
    "                \n",
    "        if jw!=0:\n",
    "            p1.next=ListNode(jw)\n",
    "        \n",
    "        return l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        carry = 0\n",
    "        head = ListNode(0)\n",
    "        pre = head\n",
    "        while l1 or l2 or carry:\n",
    "            num1 = l1.val if l1 else 0\n",
    "            num2 = l2.val if l2 else 0\n",
    "            sum = carry + num1 + num2\n",
    "            carry = sum // 10\n",
    "            pre.next = ListNode(sum % 10)\n",
    "            pre = pre.next\n",
    "            if l1:\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                l2 = l2.next\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:    \n",
    "        \n",
    "        res = []\n",
    "        j = 0\n",
    "\n",
    "        ptr1, ptr2 = l1, l2\n",
    "        while ptr1 and ptr2:\n",
    "            a, j = (ptr1.val + ptr2.val + j)%10, (ptr1.val + ptr2.val + j)//10\n",
    "            res.append(a)\n",
    "            ptr1, ptr2 = ptr1.next, ptr2.next\n",
    "\n",
    "        while ptr1:\n",
    "            x = ptr1.val\n",
    "            a, j = (x+j)%10, (x+j)//10\n",
    "            res.append(a)\n",
    "            ptr1 = ptr1.next\n",
    "        \n",
    "        while ptr2:\n",
    "            x = ptr2.val\n",
    "            a, j = (x+j)%10, (x+j)//10\n",
    "            res.append(a)\n",
    "            ptr2 = ptr2.next\n",
    "        if j!=0:\n",
    "            res.append(j)\n",
    "\n",
    "        head = ListNode()\n",
    "        ptr = head\n",
    "        for x in res:\n",
    "            ptr.next = ListNode(x)\n",
    "            ptr = ptr.next\n",
    "    \n",
    "        return head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1:\n",
    "            return l1\n",
    "        if not l2:\n",
    "            return l2\n",
    "\n",
    "        pre = 0\n",
    "        num = 0\n",
    "        dummy = ListNode(0)\n",
    "        temp = dummy\n",
    "        while l1 and l2:\n",
    "            num = l1.val + l2.val + pre\n",
    "            num1 = num%10\n",
    "            pre = num//10\n",
    "            dummy.next = ListNode(num1)\n",
    "            dummy = dummy.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        while l1:\n",
    "            num = l1.val + pre\n",
    "            num1 = num%10\n",
    "            pre = num//10\n",
    "            dummy.next = ListNode(num1)\n",
    "            dummy = dummy.next\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            num = l2.val + pre\n",
    "            num1 = num%10\n",
    "            pre = num//10\n",
    "            dummy.next = ListNode(num1)\n",
    "            dummy = dummy.next\n",
    "            l2 = l2.next\n",
    "        if pre != 0:\n",
    "            dummy.next = ListNode(pre)\n",
    "            dummy = dummy.next\n",
    "        return temp.next\n",
    "            \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        ans = ListNode(-1)\n",
    "        temp = ans\n",
    "\n",
    "        t = 0\n",
    "\n",
    "        while l1 or l2 or t != 0:\n",
    "            if l1:\n",
    "                t += l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                t += l2.val\n",
    "                l2 = l2.next\n",
    "            temp.next = ListNode(t % 10)\n",
    "            temp = temp.next\n",
    "            t //= 10\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        addons = 0\n",
    "        dump = ListNode(-1)\n",
    "        cur = dump\n",
    "        while l1 or l2:\n",
    "            v1 = 0\n",
    "            v2 = 0\n",
    "            if l1:\n",
    "                v1 = l1.val\n",
    "                l1 = l1.next\n",
    "            if l2:\n",
    "                v2 = l2.val\n",
    "                l2 = l2.next\n",
    "\n",
    "            v = v1 + v2 + addons\n",
    "            cv = v % 10\n",
    "            addons = v // 10\n",
    "            cur.next = ListNode(cv)\n",
    "            cur = cur.next\n",
    "        if addons != 0:\n",
    "            cur.next = ListNode(addons)\n",
    "        return dump.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "\n",
    "        l1.val = l1.val + l2.val\n",
    "        if l1.val >= 10:\n",
    "            l1.next = self.addTwoNumbers(l1.next, ListNode(val=l1.val // 10))\n",
    "            l1.val %= 10\n",
    "\n",
    "        l1.next = self.addTwoNumbers(l1.next, l2.next)\n",
    "        return l1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        current = ListNode()\n",
    "        result = current\n",
    "        assist = 0\n",
    "        while l1 and l2:\n",
    "            value = l1.val + l2.val + assist\n",
    "            assist = 1 if value >= 10 else 0\n",
    "            final = value - 10 if value >= 10 else value\n",
    "            current.next = ListNode(final)\n",
    "            current = current.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        \n",
    "        while l1:\n",
    "            value = l1.val + assist\n",
    "            assist = 1 if value >= 10 else 0\n",
    "            final = value - 10 if value >= 10 else value\n",
    "            current.next = ListNode(final)\n",
    "            current = current.next\n",
    "            l1 = l1.next\n",
    "\n",
    "        while l2:\n",
    "            value = l2.val + assist\n",
    "            assist = 1 if value >= 10 else 0\n",
    "            final = value - 10 if value >= 10 else value\n",
    "            current.next = ListNode(final)\n",
    "            current = current.next\n",
    "            l2 = l2.next\n",
    "        \n",
    "        if assist == 1:\n",
    "            current.next = ListNode(assist)\n",
    "        \n",
    "        return result.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        carry = 0\n",
    "        ans = ListNode(0)\n",
    "        cur_res = ans\n",
    "        cur1 = l1\n",
    "        cur2 = l2\n",
    "        while cur1 and cur2:\n",
    "            tmp = cur1.val + cur2.val + carry\n",
    "            carry = tmp // 10\n",
    "            cur_res.next = ListNode(tmp % 10)\n",
    "            cur_res = cur_res.next\n",
    "            cur1 = cur1.next\n",
    "            cur2 = cur2.next\n",
    "        while cur1:\n",
    "            tmp = cur1.val + carry\n",
    "            carry = tmp // 10\n",
    "            cur_res.next = ListNode(tmp % 10)\n",
    "            cur_res = cur_res.next\n",
    "            cur1 = cur1.next\n",
    "        while cur2:\n",
    "            tmp = cur2.val + carry\n",
    "            carry = tmp // 10\n",
    "            cur_res.next = ListNode(tmp % 10)\n",
    "            cur_res = cur_res.next\n",
    "            cur2 = cur2.next\n",
    "        if carry:\n",
    "            cur_res.next = ListNode(1)\n",
    "        return ans.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        res = ListNode(val=0, next=None)\n",
    "        cur = res\n",
    "        carry_bit = 0\n",
    "        while l1 and l2:\n",
    "            tmp = l1.val + l2.val + carry_bit\n",
    "            if tmp >= 10:\n",
    "                carry_bit = 1\n",
    "            else:\n",
    "                carry_bit = 0\n",
    "            cur.next = ListNode(val=tmp - 10) if tmp - 10 >= 0 else ListNode(val=tmp)\n",
    "            cur = cur.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        while l1:\n",
    "            tmp = l1.val + carry_bit\n",
    "            if tmp >= 10:\n",
    "                carry_bit = 1\n",
    "            else:\n",
    "                carry_bit = 0\n",
    "            cur.next = ListNode(val=tmp - 10) if tmp - 10 >= 0 else ListNode(val=tmp)\n",
    "            cur = cur.next\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            tmp = l2.val + carry_bit\n",
    "            if tmp >= 10:\n",
    "                carry_bit = 1\n",
    "            else:\n",
    "                carry_bit = 0\n",
    "            cur.next = ListNode(val=tmp - 10) if tmp - 10 >= 0 else ListNode(val=tmp)\n",
    "            cur = cur.next\n",
    "            l2 = l2.next\n",
    "        if carry_bit > 0:\n",
    "            cur.next = ListNode(val=1)\n",
    "\n",
    "\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "\n",
    "        res = ListNode(0)\n",
    "        rec = res\n",
    "        digit, acc = 0, 0\n",
    "\n",
    "        while l1 and l2:\n",
    "            s = l1.val + l2.val + acc\n",
    "            digit = s % 10\n",
    "            acc = s // 10\n",
    "            res.next = ListNode(digit)\n",
    "            res = res.next\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "        while l1:\n",
    "            s = l1.val + acc\n",
    "            digit = s % 10\n",
    "            acc = s // 10\n",
    "            res.next = ListNode(digit)\n",
    "            res = res.next\n",
    "            l1 = l1.next\n",
    "        while l2:\n",
    "            s = l2.val + acc\n",
    "            digit = s % 10\n",
    "            acc = s // 10\n",
    "            res.next = ListNode(digit)\n",
    "            res = res.next\n",
    "            l2 = l2.next\n",
    "        if acc:\n",
    "            res.next = ListNode(1)\n",
    "            res = res.next\n",
    "        return rec.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        p1, p2 = l1, l2\n",
    "        carry = 0\n",
    "        while p1 and p2:\n",
    "            p1.val += p2.val + carry\n",
    "            carry = p1.val // 10\n",
    "            p1.val = p1.val % 10\n",
    "            if not p1.next or not p2.next:\n",
    "                break\n",
    "            p1, p2 = p1.next, p2.next\n",
    "        if not p1.next: p1.next = p2.next\n",
    "\n",
    "        while p1.next and carry:\n",
    "            p1.next.val += carry\n",
    "            carry = p1.next.val // 10\n",
    "            p1.next.val %= 10\n",
    "            p1 = p1.next\n",
    "        if carry: p1.next = ListNode(carry)\n",
    "        return l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l1 == None and l2 == None:\n",
    "            return None\n",
    "        if not l1:\n",
    "            return getnum(l2)\n",
    "        if not l2:\n",
    "            return getnum(l1)\n",
    "        def getnum(l):\n",
    "            res = 0\n",
    "            cnt = 0\n",
    "            while l:\n",
    "                res += l.val * (10**cnt)\n",
    "                cnt += 1\n",
    "                l = l.next\n",
    "            return res\n",
    "        \n",
    "        t1 = getnum(l1)\n",
    "        print(t1)\n",
    "        t2 = getnum(l2)\n",
    "        print(t2)\n",
    "        def create(nums):\n",
    "            dummy = ListNode(-1)\n",
    "            p = dummy\n",
    "            for i in (nums):\n",
    "                t = ListNode(int(i))\n",
    "                p.next = t\n",
    "                p = p.next\n",
    "            return dummy.next\n",
    "        return create(list(str(t1+t2))[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head = ListNode(0)\n",
    "        node = head\n",
    "        remaining = 0\n",
    "        while l1 or l2:\n",
    "            if l1 == None:\n",
    "                node.next = l2\n",
    "                l1 = ListNode(0)\n",
    "            if l2 == None:\n",
    "                node.next = l1\n",
    "                l2 = ListNode(0)\n",
    "            remaining += l1.val + l2.val\n",
    "            node.next = ListNode(remaining % 10)\n",
    "            remaining = remaining // 10 \n",
    "            node = node.next\n",
    "            l1 = l1.next \n",
    "            l2 = l2.next \n",
    "        if remaining:\n",
    "            node.next = ListNode(remaining)\n",
    "        return head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        dummyhead=ListNode()\n",
    "        pre=dummyhead\n",
    "        p=0\n",
    "        while l1 or l2 or p>0:\n",
    "            temp=0\n",
    "            if l1:\n",
    "                temp+=l1.val\n",
    "                l1=l1.next\n",
    "            if l2:\n",
    "                temp+=l2.val\n",
    "                l2=l2.next\n",
    "            node=ListNode((temp+p)%10)\n",
    "            pre.next=node\n",
    "            pre=node\n",
    "            p=(temp+p)//10\n",
    "        return dummyhead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head = ListNode(-1)\n",
    "        p = head # pointer\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry: # 还有l1、l2或者carry    \n",
    "            n = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry # l1值+l2值+carry\n",
    "            carry = n // 10  # 取十位上的数\n",
    "            p.next = ListNode(n % 10)\n",
    "            p = p.next\n",
    "            l1, l2 = l1.next if l1 else None, l2.next if l2 else None\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        num1, num2 = 0, 0\n",
    "        n1 = l1\n",
    "        n2 = l2\n",
    "        c = 0\n",
    "        while n1:\n",
    "            num1 += n1.val * 10 ** c \n",
    "            n1 = n1.next\n",
    "            c += 1\n",
    "\n",
    "        c2 = 0\n",
    "        while n2:\n",
    "            num2 += n2.val * 10 ** c2 \n",
    "            n2 = n2.next\n",
    "            c2 += 1\n",
    "\n",
    "        res = str(num1 + num2)\n",
    "\n",
    "        print(res, num1, num2)\n",
    "\n",
    "        result = ListNode(0)\n",
    "        r = result\n",
    "        i = 0\n",
    "        for i in range(len(res)):\n",
    "            cur = ListNode(int(res[i]))\n",
    "            cur.next = result.next\n",
    "            result.next = cur\n",
    "\n",
    "        return result.next\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        arr = []\n",
    "        \n",
    "        cur = l1 \n",
    "        while cur: \n",
    "            arr.append(str(cur.val))\n",
    "            cur = cur.next \n",
    "        num1 = int(''.join(arr[::-1]))\n",
    "            \n",
    "        arr = []\n",
    "        cur = l2 \n",
    "        while cur: \n",
    "            arr.append(str(cur.val))\n",
    "            cur = cur.next \n",
    "        num2 = int(''.join(arr[:: -1]))\n",
    "        \n",
    "        res = list(str(num1+num2))\n",
    "        # print(res)\n",
    "        pseudo_head = ListNode(next=l1)\n",
    "        cur = pseudo_head.next \n",
    "        while res:\n",
    "            cur.val = int(res.pop())\n",
    "            if res and cur.next is None:\n",
    "                cur.next = ListNode(val=None, next=None)\n",
    "            cur = cur.next\n",
    "\n",
    "        return pseudo_head.next "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head = ListNode(val = 0)\n",
    "        res = head\n",
    "\n",
    "        ex = 0\n",
    "        while l1 or l2:\n",
    "            num1 = l1.val if l1 else 0\n",
    "            num2 = l2.val if l2 else 0\n",
    "\n",
    "            e = ListNode()\n",
    "            e.val = (num1+num2+ex)%10\n",
    "            ex = (num2+num1+ex)//10\n",
    "            head.next = e\n",
    "            l1= l1.next if l1 else None\n",
    "            l2=l2.next if l2  else None\n",
    "            head = head.next\n",
    "        if ex :\n",
    "            head.next = ListNode(ex)\n",
    "        return res.next\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head = ListNode(-1)\n",
    "        p = head\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:            \n",
    "            n = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry = n // 10  \n",
    "            p.next = ListNode(n % 10)\n",
    "            p = p.next\n",
    "            l1, l2 = l1.next if l1 else None, l2.next if l2 else None\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        num1=k=0\n",
    "        while l1:\n",
    "            num1+=l1.val*10**k\n",
    "            k+=1\n",
    "            l1=l1.next\n",
    "        num2=k=0\n",
    "        while l2:\n",
    "            num2+=l2.val*10**k\n",
    "            k+=1\n",
    "            l2=l2.next\n",
    "        num=num1+num2\n",
    "        dummyhead=ListNode()\n",
    "        pre=dummyhead\n",
    "        while num:\n",
    "            a=num%10\n",
    "            num//=10\n",
    "            node=ListNode(a)\n",
    "            pre.next=node\n",
    "            pre=node\n",
    "        if not dummyhead.next:\n",
    "            dummyhead.next=ListNode(0)\n",
    "        return dummyhead.next \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        carry = 0\n",
    "        final = ListNode(0)\n",
    "        result = final\n",
    "        while l1 or l2:\n",
    "            if l1 and l2:\n",
    "                final.next = ListNode((l1.val+l2.val+carry) % 10)\n",
    "                final = final.next\n",
    "                carry = (l1.val+l2.val+carry) // 10\n",
    "                l1 = l1.next\n",
    "                l2 = l2.next\n",
    "            elif l1:\n",
    "                final.next = ListNode((l1.val + carry) % 10)\n",
    "                carry = (l1.val + carry) // 10\n",
    "                l1 = l1.next\n",
    "                final = final.next\n",
    "            else:\n",
    "                final.next = ListNode((l2.val + carry) %10)\n",
    "                carry = (l2.val + carry) // 10\n",
    "                l2 = l2.next\n",
    "                final = final.next\n",
    "        if carry == 1:\n",
    "            final.next = ListNode(1)\n",
    "\n",
    "        return result.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head = ListNode(-1)\n",
    "        p = head\n",
    "        carry = 0\n",
    "        while l1 or l2 or carry:            \n",
    "            n = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
    "            carry = n // 10  # 取十位上的数\n",
    "            p.next = ListNode(n % 10)\n",
    "            p = p.next\n",
    "            l1, l2 = l1.next if l1 else None, l2.next if l2 else None\n",
    "        return head.next\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        res=ListNode(-1)\n",
    "        cur=res\n",
    "        carry=0\n",
    "        while l1 or l2 or carry:\n",
    "            sum= (l1.val if l1 else 0) + (l2.val if l2 else 0) +carry\n",
    "            cur.next=ListNode(sum%10)\n",
    "            cur=cur.next\n",
    "            carry=sum//10\n",
    "            l1=l1.next if l1 else None\n",
    "            l2=l2.next if l2 else None\n",
    "        return res.next\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        l1_cur, l2_cur = l1, l2\n",
    "        sum = l1_cur.val + l2_cur.val\n",
    "        carry = 1 if sum >= 10 else 0\n",
    "        result_head = ListNode(sum % 10)\n",
    "        result = result_head\n",
    "        l1_cur, l2_cur = l1_cur.next, l2_cur.next\n",
    "        while l1_cur and l2_cur:\n",
    "            sum = l1_cur.val + l2_cur.val + carry\n",
    "            result.next = ListNode(sum % 10)\n",
    "            carry = 1 if sum >= 10 else 0\n",
    "            result = result.next\n",
    "            l1_cur, l2_cur = l1_cur.next, l2_cur.next\n",
    "        while l1_cur:\n",
    "            sum = l1_cur.val + carry\n",
    "            result.next = ListNode(sum % 10)\n",
    "            carry = 1 if sum >= 10 else 0\n",
    "            result = result.next\n",
    "            l1_cur = l1_cur.next\n",
    "        while l2_cur:\n",
    "            sum = l2_cur.val + carry\n",
    "            result.next = ListNode(sum % 10)\n",
    "            carry = 1 if sum >= 10 else 0\n",
    "            result = result.next\n",
    "            l2_cur = l2_cur.next\n",
    "        if carry == 1:\n",
    "            result.next = ListNode(1)\n",
    "        return result_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        head =res=ListNode(-1)\n",
    "        nxt_v=0\n",
    "        while l1 and l2:\n",
    "            v1 = l1.val\n",
    "            v2 = l2.val\n",
    "            res_v = (v1+v2+nxt_v)%10\n",
    "            nxt_v = (v1+v2+nxt_v)//10\n",
    "            res.next = ListNode(res_v)\n",
    "            res = res.next\n",
    "            l1=l1.next\n",
    "            l2=l2.next\n",
    "        while  l1:\n",
    "            res_v = (l1.val+nxt_v)%10\n",
    "            nxt_v = (l1.val+nxt_v)//10\n",
    "            res.next = ListNode(res_v)\n",
    "            res = res.next\n",
    "            l1=l1.next\n",
    "        while  l2:\n",
    "            res_v = (l2.val+nxt_v)%10\n",
    "            nxt_v = (l2.val+nxt_v)//10\n",
    "            res.next = ListNode(res_v)\n",
    "            res = res.next\n",
    "            l2=l2.next\n",
    "        if nxt_v:\n",
    "            res.next = ListNode(nxt_v )\n",
    "        return  head.next\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
